javascript - Why is Array.splice() so slow? - Stack Overflow

admin管理员组

文章数量:1344232

I recently saw this benchmark:

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.

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

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

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.

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

• javascript
• arrays
• performance
• time

Share Improve this question Follow asked Jun 9, 2015 at 23:07 Stack TracerStack Tracer 1,0281010 silver badges2727 bronze badges 4

• 2 Compare their algorithms: splice, and pop. – Sampson Commented Jun 9, 2015 at 23:15
• " than a for loop iterating through the elements" --- you don't have any loops in your jsperf example tests – zerkms Commented Jun 9, 2015 at 23:15
• If you are going to pare the speed of different algorithms, you should start by having them all do the same thing. The linked code doesn't do that, each snippet has a different result. – RobG Commented Jun 9, 2015 at 23:52
• pop() just shortens the array from the end,;most of the array is unchanged, whereas that splice() pulls from the front, demanding the whole array be re-indexed. – dandavis Commented Jun 10, 2015 at 0:57

Add a ment  | 

3 Answers 3

Sorted by: Reset to default 6

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.

Conversely, this piece of code:

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

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 acplish the declared goal, since it changes the order of elements in the array (!). Compare:

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

with:

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

splice will return your entire array, less the deleted item. So for the 1 element in the benchmark example, you have to copy the other 499999 elements to a new array. But pop just has to shorten the array by one element.

Here are some measures from a real project (not a benchmark). I had a list of objects in an array and had to end up with a smaller subset. In the case shown here, the list happened to have 17,000 items and we happened to need just 7.

My first approach was to iterate through the array and use splice to remove those not needed. Firefox had major problems with that approach, taking over 12 seconds to do what Chrome did in 0.09 seconds! The second approach was to iterate in reverse, doing the same. The third was to copy the wanted objects to a new array.

              Splice Forward   Splice Reverse   Copy to Array   (time in milliseconds)
Chrome 51             91              64             47
IE 11.0.31           309             144             31
Firefox 47        12,544              61             21

In the end, copying was much faster for all the browsers.

However, if you do need to splice, doing it in reverse may be much faster.

本文标签： javascriptWhy is Arraysplice() so slowStack Overflow