Hey, let’s say that I have a list of indexes that I want to remove from array. What’s the most performant way to do this? I don’t need to check any conditions (no need to loop through whole array), I already know all the indexes that I want to remove. I also know a list of items that I want to remove (let’s say some Transform values).
We can’t just easily subtract one array from another, so other options:
Reverse foreach loop and checking if current index is present in an indexesToRemove] array, but this involves looping through whole array == performance hit with larger arrays
Since I also know what items I want to remove (list of Transform values), maybe… Foreach(transformsToRemove]) { myArray.RemoveItem(transform); } … ? Will it be better than the first option? It would not need to loop through whole array, but is the *RemoveItem *function heavy?
… Or maybe there are some better solutions for this? I would be grateful for some hints.
I never checked how arrays are implemented in blueprints, I did only hear they’re quite complex. But I would expect 2. is inefficient. I am pretty sure RemoveItem needs a loop over the whole array each time.
is definitely more efficient but why don’t you just call RemoveIndex for each item you want to remove? 1. uses the RemoveIndex node anyway, doesn’t it?
You wrote you already know the indices. The reverse ForEachLoop is unnecessary so. You would only need to make sure you remove the indices in descendant order, but I’m sure you know that.
You’re right, it should work with foreach(index in indicesToRemove]) { myArray.RemoveIndex(index); } , but the indicesToRemove] would need to be sorted in descending order to prevent getting wrong indices after using RemoveIndex…
… I would need to make my own Sort function then, since Blueprints don’t have it by default - I should handle this, I was just afraid that sorting int array would add more performance hit compared to RemoveItem option, but if RemoveItem iterates through whole array (I don’t know how it’s built internally, but I should have guessed that ) then probably that’s the best way.
I’ll try to implement this soon, thank you!
Iterating through the whole array is how I would’ve implemented a RemoveItem node. You could create a data structure that handles RemoveItem more efficiently but that would make adding elements to the array way more costly. I seriously doubt Epic has implemented it that way.
How many items do you need frequently to remove from the array? Sorting an array is pretty easy using the MaxOfIntArray node. That’s not very efficient but no problem when you don’t want to remove really many elements frequently. And if you want to remove many I could help you by showing how to implement Quicksort in blueprints. I just created that for my Classic TopDown Fog of War.
I suspect that in most cases it will be like 500-1000 indices to remove, executed 10-15 times from different actors, but not frequently - actually just once, every time my game loads a new level, which should be a really non-frequent event in most cases and I can afford some ‘loading lag’, I’m just trying to minimize it… So not something crazy like every tick
Do you think that Quicksort would make noticeable difference compared to the MaxOfIntArray sorting (I guess that it would involve adding max element to a new sorted array and removing it from the initial one, then repeat) in this case? Thanks!
The runtime of Quicksort scales on average with nlog2(n) for n elements to sort. The runtime of a sorting algorithm using the MaxOfIntArray node scales always with nn/2. So yes, the difference is actually huge.
) then probably that’s the best way.