Array 函数的 JavaScript 运行时复杂性 [英] JavaScript runtime complexity of Array functions

问题描述

JS标准对常见的Array函数(如push、pop、shift)定义的运行时复杂度，slice 还是 splice?特别是我有兴趣在随机位置删除和插入条目.如果未定义复杂性，我可以期待什么，例如在 V8 中?

Is the runtime complexity defined by the JS standard on common Array functions like push, pop, shift, slice or splice? Esp. I'm interested in removing and inserting entries at random positions. If the complexity is not defined, what can I expect, e.g. in V8?

(这个问题的灵感来自 this.另外，这个基准，发布了这里，也让我好奇，但也许这是一些不相关的现象.)

(This question was inspired by this. Also, this benchmark, posted here, also makes me curious, but maybe that is some unrelated phenomena.)

(一个非常相关的问题是这里.但是，关于接受的答案说它现在是错误的.此外，接受的答案没有任何参考标准真正以这种方式定义它.).

(A very related question is here. 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.).

推荐答案

ECMA 规范没有指定边界复杂度，但是，您可以从规范的算法中推导出一个边界复杂度.

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

push 是 O(1)，但是，在实践中，它会在引擎定义的边界处遇到 O(N) 复制成本为插槽数组需要重新分配.这些边界通常是对数的.

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 是 O(1) 与 push 类似的警告，但 O(N) 复制很少遇到，因为它经常被折叠到垃圾收集中(例如，复制收集器只能复制数组的已使用部分).

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 最差 O(N) 但在特殊情况下，它可以实现为 O(1)减慢索引速度，因此您的里程可能会有所不同.

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 是 O(N) 其中 N 是 end - start.如果没有显着减慢对两个阵列的写入速度，这里的优化机会并不多.

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 是，最坏的情况，O(N).有一些数组存储技术将 N 除以一个常数，但它们会显着减慢索引速度.如果引擎使用此类技术，您可能会注意到操作异常缓慢，因为它会在访问模式更改触发的存储技术之间切换.

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.

你没有提到的是sort.在平均情况下，O(N log N).但是，根据引擎选择的算法，在某些情况下您可能会得到 O(N^2).例如，如果引擎使用 QuickSort(即使延迟到 InsertionSort)，它也有众所周知的 N^2 个案例.这可能是您的应用程序的 DoS 来源.如果这是一个问题，请限制您排序的数组的大小(可能合并子数组)或救助到 HeapSort.

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.

这篇关于Array 函数的 JavaScript 运行时复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！