为什么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