Array 函数的 JavaScript 运行时复杂度

运行时的复杂性是否由 JS 标准定义在诸如 push、 pop、 shift、 slice或 splice这样的常见 Array函数上？ESP.我感兴趣的是在任意位置移除和插入条目。如果没有定义复杂性，我能期望什么，例如在 V8中？

(这个问题的灵感来自 这个。另外，发表在 给你上的 这个基准也让我感到好奇，但也许这是一些不相关的现象。)

(A very related question is 给你. However, one of the comments on the accepted answer says that it is wrong now. Also, the accepted answer does not have any reference that the standard really defines it that way.).

62163 次浏览
小开
最佳答案

The ECMA specification does not specify a bounding complexity, however, you can derive one from the specification's algorithms.

push is O(1), however, in practice it will encounter an O(N) copy costs at engine defined boundaries as the slot array needs to be reallocated. These boundaries are typically logarithmic.

pop is O(1) with a similar caveat to push but the O(N) copy is rarely encountered as it is often folded into garbage collection (e.g. a copying collector could only copy the used part of an array).

shift is at worst O(N) however it can, in specially cases, be implemented as O(1) at the cost of slowing down indexing so your mileage may vary.

slice is O(N) where N is end - start. Not a tremendous amount of optimization opportunity here without significantly slowing down writes to both arrays.

splice is, worst case, O(N). There are array storage techniques that divide N by a constant but they significantly slow down indexing. If an engine uses such techniques you might notice unusually slow operations as it switches between storage techniques triggered by access pattern changes.

One you didn't mention, is sort. It is, in the average case, O(N log N). However, depending on the algorithm chosen by the engine, you could get O(N^2) in some cases. For example, if the engine uses QuickSort (even with an late out to InsertionSort), it has well-known N^2 cases. This could be a source of DoS for your application. If this is a concern either limit the size of the arrays you sort (maybe merging the sub-arrays) or bail-out to HeapSort.

小开

slice is only linear if the number be taken is unknown. If the slice number is constant, then slice is constant, not linear.

小开

Just a side note, it is possible to implement shift / unshift, push / pop methods in O(1) using RingBuffer (i.o.w CircularQueue / CircularBuffer) data structure. It would be O(1) for worst case whenever the circular buffer is not required to grow. Did anyone actually measure performance of these operations? It's always better know rather than to guess...

小开

in very simple words

push -> O(1)

pop -> O(1)

shift -> O(N)

slice -> O(N)

splice -> O(N)

Here is a complete explanation about time complexity of Arrays in JavaScript.


提交答案