为什么Array.splice()这么慢? [英] Why is Array.splice() so slow?

问题描述

我最近看到了这个基准: http://jsperf.com/删除元素拼接与移动并弹出

I recently saw this benchmark: http://jsperf.com/remove-element-splice-vs-move-and-pop

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

I noticed that Array.splice() is several orders of magnitude slower than a for loop iterating through the elements. This lead me to wonder why Array.splice() is so slow.

因此，我来​​这里问你:为什么Array.splice()这么慢?

Therefore, I came here to ask you: Why is Array.splice() so slow?

推荐答案

该基准测试有一个谬误: .splice 保留数组中元素的顺序，因此需要移动一半直到通过移除创建的孔被筛选到末端为止，并且可以通过调整数组的大小来移除.因此， .splice 在线性时间中工作.

There is a fallacy in that benchmark: .splice preserves the order of the elements in the array, and therefore needs to move half of the elements until the hole created by the removal is sifted up to the end and can be removed by resizing the array. It follows that .splice works in linear time.

相反，这段代码:

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

用要删除的元素交换最后一个元素，并缩短1个元素的数组，此操作可以在恒定时间内完成.从技术上讲，上面的代码段甚至都没有实现声明的目标，因为它会更改数组中元素的顺序(！).比较:

swaps the last element with the one to be removed, and shortens the array of 1 element, an operation that can be done in constant time. Technically, the snippet above does not even accomplish the declared goal, since it changes the order of elements in the array (!). Compare:

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

具有:

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

这篇关于为什么Array.splice()这么慢?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！