javascript - 为什么 Array.splice() 这么慢？

Question

我最近看到了这个基准:http://jsperf.com/remove-element-splice-vs-move-and-pop

我注意到 Array.splice() 比遍历元素的 for 循环慢几个数量级。这让我想知道为什么 Array.splice() 这么慢。

所以特意过来问你:为什么Array.splice()这么慢？

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