阵列功能的JavaScript运行的复杂性 [英] JavaScript runtime complexity of Array functions

问题描述

是由共同的阵列函数的JS标准像定义运行时的复杂性推，弹出，移，片或拼接？ ESP。我感兴趣的去除，并在随机位置插入项。如果复杂性没有定义的，我有什么可以期待，例如在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?

（这个问题是由<一个启发href=\"http://stackoverflow.com/questions/1344500/efficient-way-to-insert-a-number-into-a-sorted-array-of-numbers\">this.此外，这个基准，发布<一个href=\"http://stackoverflow.com/questions/614126/why-is-array-push-sometimes-faster-than-arrayn-value/14997768\">here,也让我好奇，但也许这是一些无关的现象。）

(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.

推是的 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.

弹出是的 O（1）的一个类似的告诫推但的 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).

移在最坏的 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.

片是的 O（N）的，其中的 N 的是结束 - 启动。没有显著减缓的优化在这里没有机会了大量写入到两个阵列。

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.

拼接是，最坏的情况下，的 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.

一，你不提，是排序。这是，在平均情况下，的 O（N日志N）的。但是，根据由发动机选择的算法上，你可以得到的 O（N ^ 2）的在某些情况下。例如，如果引擎使用快速排序（即使是使用一个晚出插入排序），它已公知的 N ^ 2 的情况。这可能是拒绝服务，为您的应用程序的来源。如果这是一个问题要么限制你排序（也许合并子阵）的数组的大小或纾困，以堆排序。

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.

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