从数组中删除的最有效方法是什么？

Question

我在一个HTML5游戏中有一个包含粒子（火，血，烟等）的数组。所有粒子都有过期/寿命。我每帧以60fps创建多达100个粒子，因此我希望尽可能保持这个数组干净，以便可以高效地循环遍历它。

我听说使用“splice”而不是“delete”从数组中删除元素更好。对我来说，这很有道理，因为我不想循环遍历留下空白键的数组。

然而，我测试了一下，如果我用“delete”而不是拼接来删除过期的粒子，则帧率更高，更稳定。缺点是游戏运行时间越长，我的粒子数组就会变得越长。

这个问题有更好的解决方案吗？

- Sam

---

问题是，您是否接受将索引设置为未定义，还是要完全删除该索引并重新索引数组？在数组中，“delete”实际上并不真正删除，它只是设置为“undefined”，因此您必须决定是否可以接受。没有什么神奇的方法，您只能将数组拼接成一个新数组，或者删除并卡在“undefined”值上。 - adeneo

无论未定义是否可接受，这就是我的问题。数组的顺序并不重要。只需要一个巨大的粒子列表来更新和绘制。 - Sam

这取决于您正在做什么，不容易回答。在某些情况下，使用 slice 更好，以避免迭代未定义的索引，而在其他情况下，这些无关紧要，或者您可以在迭代之前运行 Array.filter 并删除未定义的索引，速度取决于具体情况。 - adeneo

请注意，如果您需要从数组的开头或结尾删除元素，则“shift”或“pop”可能是最快的方法。 - adeneo

Answer 1

如果数组中的项目顺序不重要，那么只需将数组中的最后一个项目分配给你想要覆盖的项目，然后通过减少.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;
}

这种方法更快，因为它不需要重新索引，并且适用于无需考虑顺序的情况。

- six fingered man

Answer 2

当你在数组元素上使用delete时，实际上你所做的就是将该数组元素设置为undefined。数组仍将保持相同的长度。当你使用splice时，你实际上完全删除了该元素。该元素被删除，其后的所有元素都向下移动一个索引位置。在这两者之间，delete会更快，因为你的数组不必重新索引。

至于性能方面，如果将已删除的元素保留为undefined可行，则这可能是最好的方法。如果你担心数组长度过长，或者经常需要搜索该数组并希望减少开销，则可以定期使用filter过滤掉未定义的元素，如下所示：

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

var interval = setInterval(filterArr, 5000);

这将为你带来最好的双重效果。 当你需要删除粒子时，使用delete将元素设置为undefined，比原地删除更快。 偶尔，你会原地删除它们以保持数组大小更小。

根据你的需求，你可以改进这一点。 祝你好运 :)

- user3886234

---

实际上，filter 已经跳过了未定义的元素，所以您可以这样做：function filterArr(a) { return a.filter(function() { return true; }); }。 - user663031

Answer 3

通过自己打包数组，您将获得更高的性能：操作更少，无需处理当前数组并创建新数组（就像Array.filter一样），因此垃圾收集也会减少很多。

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 ;
}

- GameAlchemist

---

我猜这比减少 4 帧的方法更有效解决问题;-)另外，我在这里有一个粒子引擎:https://gamealchemist.wordpress.com/2013/06/16/introducing-jsparkle-a-versatile-and-fast-javascript-particle-engine/，它使用旋转缓冲区（更快...但是您有一个最大计数...），以及一些关于对象池的建议：https://gamealchemist.wordpress.com/2013/02/02/no-more-garbage-pooling-objects-built-with-constructor-functions/祝您编码愉快！ - GameAlchemist

这里有一个JSPerf，将其与类似问题的答案进行比较：http://jsperf.com/splice-vs-pack/11对于小数组，这种方法并不必要。但对于非常大的数组，它更加高效。 - Ali Ok

顺便提一下，效率取决于要删除的元素数量。如果要删除的元素不太多，则倒序拼接比构建新数组或将其设置为未定义并压缩数组更好。 - Ali Ok

请纠正我，但我认为 dstIndex--; 不正确。它应该被省略。如果 tgtArray 有一个元素并且它是活动的，那么这个方法将截断它。 - Yousif Al-Y