Most efficient way to delete from array?

Question

I have an array containing particles (fire, blood, smoke, etc.) in an HTML5 game. All particles have an expiry/lifespan. I'm creating up to 100 particles per frame at 60fps so I want to keep this array as clean as possible so I can loop through it efficiently.

I have heard it's better to use 'splice' rather than 'delete' to remove elements from an array. This makes sense to me as I'd rather not loop through keys of the array that are blank (that 'delete' leaves behind).

However, I tested this out and have a higher, more consistent frame rate if I 'delete' keys rather than splicing them to remove expired particles. The downside is the longer the game runs the longer my particles array gets.

Is there a better solution to this?

The question is, are you fine with the index being set to undefined, or do you want to remove that index entirely and reindex the array? `delete` doesn't really delete in arrays, it just sets to `undefined`, so you have to decide wether or not that is acceptable. There's no magic method, you either splice the array into a new one, or you delete and get stuck with an `undefined` value — adeneo, Feb 08 '15 at 22:42
Whether or not undefined is acceptable is pretty much what I'm asking. The order of the array does not matter. Just a giant list of particles that need to be updated and drawn. — Sam, Feb 08 '15 at 22:44
That depends on you, on what you're doing, and is not easy to answer. In some cases `slice` would be better to avoid iterating over undefined indices, in other cases those don't matter, or you can run `Array.filter` before iterating and remove the undefined indices, what's faster depends ? — adeneo, Feb 08 '15 at 22:46
Note that if you have to remove from the beginning or end of the array, `shift` or `pop` is probably the fastest. — adeneo, Feb 08 '15 at 22:47

score 4 · Answer 1 · answered Feb 08 '15 at 22:44

If the order of the items in the array doesn't matter, then simply assign the last item in the array to the one you want to overwrite and then delete it by reducing the .length.

function unordered_remove(arr, i) {
    if (i <= 0 || i >= arr.length) {
        return;
    }
    if (i < arr.length - 1) {
        arr[i] = arr[arr.length-1];
    }
    arr.length -= 1;
}

This is much faster because it doesn't need to reindex and is good for situations where the order doesn't matter.

score 2 · Answer 2 · answered Feb 08 '15 at 23:00

When you use delete on an array element, all you are actually doing is setting that array element to undefined. The array will still have the same length. When you use splice, you actually remove that element entirely. The element is removed, and everything after that element is shifted down 1 index.Of the two, delete is going to be faster since your array doesn't have to re-index.

As for performance, if leaving the deleted elements as undefined works, then that is probably the best way to do it. If you are concerned about the array length growing too long, or maybe have to search that array frequently and want to reduce overhead, you could periodically filter out the undefined elements like so:

function filterArr() {
    myArr = myArr.filter(function(v) {
       return typeof v !== 'undefined';
    });
}

var interval = setInterval(filterArr, 5000);

This will give you the best of both worlds. When you need to remove the particles, you use delete to set the elements to undefined, which is faster than removing them in place. Every now and then, you remove them in place to keep your array size lower.

You could improve upon that depending on your requirements. Good luck :)

Actually, filter already skips over undefined elements, so you can just do `function filterArr(a) { return a.filter(function() { return true; }); }`. — , Aug 14 '15 at 03:55

GameAlchemist · Accepted Answer · 2015-02-09T12:33:01.707

1

You'll have way higher performances by packing the array by yourself : less operations AND no need to dispose current array and create a new one (like Array.filter does), so much less garbage collection.

function packArray(tgtArray) {
   if (!tgtArray || !tgtArray.length) return;
   var srcIndex = 0;
   var dstIndex = 0;
   var arrayLength = tgtArray.length ;
   do {
       var currentItem = tgtArray[srcIndex]; 
       if (currentItem.alive) {
         if (srcIndex != dstIndex) {
            tgtArray[dstIndex] = currentItem ;
         }
         dstIndex++;
       } 
       srcIndex++;
   } while (srcIndex != arrayLength) ;
    dstIndex--;
    tgtArray.length = dstIndex > 0 ? dstIndex : 0 ;
}

edited Feb 09 '15 at 12:33

answered Feb 09 '15 at 12:27

GameAlchemist

18,995
7
36
59

So i guess this is more a solution than the -4fps one ;-) By the way i have a particle engine here :https://gamealchemist.wordpress.com/2013/06/16/introducing-jsparkle-a-versatile-and-fast-javascript-particle-engine/ that uses a rotating buffer (even faster... but you have a max count...), and some advices on pooling here : https://gamealchemist.wordpress.com/2013/02/02/no-more-garbage-pooling-objects-built-with-constructor-functions/ Happy coding ! – GameAlchemist Feb 09 '15 at 20:43
Here is a JSPerf comparing this with answer of a [similar question](http://stackoverflow.com/a/9287469/768685) : http://jsperf.com/splice-vs-pack/11 For small arrays this approach is just not necessary. For very large arrays, it is much more efficient. – Ali Ok Mar 01 '16 at 23:05
BTW, efficiency depends on the number of elements to delete. If not too many to delete, then splicing in reverse order is better than building a new array or setting to undefined and then packing the array. – Ali Ok Mar 01 '16 at 23:14
Correct me if I'm wrong, but I don't think the `dstIndex--;` is correct. It should be omittted. If `tgtArray` has one element and it's alive, then this method would truncate it. – Yousif Al-Y Aug 16 '18 at 17:28

Most efficient way to delete from array?

3 Answers3

Linked