为什么Array.splice()方法很慢？

Question

我最近看到这个基准测试：http://jsperf.com/remove-element-splice-vs-move-and-pop 我注意到，Array.splice()的速度比通过循环遍历元素要慢几个数量级。这让我想知道为什么Array.splice()如此缓慢。

因此，我来问你：为什么Array.splice()如此缓慢？

- Stack Tracer

---

比较它们的算法：splice 和 pop。 - Sampson

"比起使用for循环遍历元素，你的jsperf示例测试中没有任何循环。" - zerkms

如果你要比较不同算法的速度，你应该让它们都做同样的事情。链接的代码并没有这样做，每个片段都有不同的结果。 - RobG

pop() 只是从末尾缩短数组，大部分数组保持不变，而splice()则从前面拉取，要求整个数组重新索引。 - dandavis

Answer 1

这个基准测试中存在一个谬误：.splice 会保留数组元素的顺序，因此需要移动一半的元素，直到由删除操作创建的空洞被过滤到末尾并可以通过调整数组大小来删除。因此，.splice 可以在线性时间内工作。

相反，下面这段代码：

array[500000] = array[array.length-1];
array.pop();

交换最后一个元素和要删除的元素，并将数组缩短1个元素，这是可以在常数时间内完成的操作。从技术上讲，上面的代码片段甚至没有实现声明的目标，因为它改变了数组中元素的顺序！请参考：

> array.splice(500000,1)
> console.log(array[500000])
500001

使用：

> array[500000] = array[array.length-1];
> array.pop();
> console.log(array[500000])
999999

- Stefano Sanfilippo

Answer 2

splice会返回删除所选项目后的整个数组。因此，在基准示例中的1个元素中，您需要将其他499999个元素复制到新数组中。但pop只需要将数组缩短一个元素。

- Kim Ryan

---

splice 不会返回整个数组，也不会复制整个数组，请查看文档。 - Stefano Sanfilippo

是的，没错，只需要一个副本而不是我之前说的 499999 个。但根据这里的内容，它仍然返回一个数组 https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/splice。如果它只有一个元素，那么内存开销应该类似于 pop 操作，但仍然比返回一个变量多一些工作量。 - Kim Ryan

@StefanoSanfilippo——根据语言规范，splice算法中的第二步是：“让A成为一个新数组…”。它创建一个新数组并将删除的元素复制到其中，然后返回该新数组。 - RobG

Answer 3

这里有一些来自实际项目（不是基准测试）的措施。我有一个对象列表，需要从中得到一个较小的子集。在这个示例中，列表恰好有17,000个项目，我们只需要7个。

我的第一种方法是遍历数组并使用splice删除不需要的元素。Firefox对此方法存在严重问题，用了12秒多的时间，而Chrome只用了0.09秒！第二种方法是反向迭代，执行相同的操作。第三种方法是将所需的对象复制到新数组中。

最终，对于所有浏览器来说，复制都更快。

但是，如果确实需要使用splice，那么在反向操作可能会更快。

- Glen Little

---

数组中的对象非常简单，包含3个字符串和1个数字。 - Glen Little

你还记得复制子集的更快方法吗？我使用切片从数组开头删除x个元素，但这在繁重的工作流程中有点成为瓶颈。 - Tiago

@Tiago 我想我最终没有改变原始数组，只是将我需要的内容复制到一个新数组中，然后放弃/删除了原始数组。 - Glen Little