Big O of JavaScript arrays

Arrays in JavaScript are very easy to modify by adding and removing items. It somewhat masks the fact that most languages arrays are fixed-size, and require complex operations to resize. It seems that JavaScript makes it easy to write poorly performing array code. This leads to the question:

What performance (in terms of big O time complexity) can I expect from JavaScript implementations in regards to array performance?

I assume that all reasonable JavaScript implementations have at most the following big O's.

Access - O(1)
Appending - O(n)
Prepending - O(n)
Insertion - O(n)
Deletion - O(n)
Swapping - O(1)

JavaScript lets you pre-fill an array to a certain size, using new Array(length) syntax. (Bonus question: Is creating an array in this manner O(1) or O(n)) This is more like a conventional array, and if used as a pre-sized array, can allow O(1) appending. If circular buffer logic is added, you can achieve O(1) prepending. If a dynamically expanding array is used, O(log n) will be the average case for both of those.

Can I expect better performance for some things than my assumptions here? I don't expect anything is outlined in any specifications, but in practice, it could be that all major implementations use optimized arrays behind the scenes. Are there dynamically expanding arrays or some other performance-boosting algorithms at work?

P.S.

The reason I'm wondering this is that I'm researching some sorting algorithms, most of which seem to assume appending and deleting are O(1) operations when describing their overall big O.

43746

小开

保证

对于任何数组操作，都没有指定的时间复杂度保证。数组的执行方式取决于引擎选择的底层数据结构。引擎也可能具有不同的表示形式，并根据某些启发式方法在它们之间切换。初始数组大小可能是启发式的，也可能不是。

现实

例如，V8使用(到目前为止) Hashtables和数组列表来表示数组。它还具有各种不同的对象表示形式，因此不能比较数组和对象。因此数组访问总是优于 O (n) ，而且 也许吧甚至和 C + + 数组访问一样快。附加为 O (1) ，除非您达到了数据结构的大小，并且它必须缩放(即 O (n))。假装更糟。如果您执行类似 delete array[index]的操作，删除操作可能会更糟糕(不要!)因为这可能会迫使引擎改变它的表示。

建议

对数值数据结构使用数组。这就是它们存在的意义。这就是引擎优化它们的目的。避免使用稀疏数组(或者如果必须使用稀疏数组，可能会导致性能下降)。避免使用混合数据类型的数组(因为这使得内部表示更复杂)。

如果您真的想为某个引擎(和版本)进行优化，请检查其源代码以获得绝对答案。

最佳答案

_{注意: 虽然这个答案在2012年是正确的，但是今天的引擎对对象和数组使用了非常不同的内部表示。这个答案可能正确，也可能不正确。}

与大多数语言不同的是，在 Javascript 数组中实现带有数组的数组是对象，值存储在哈希表中，就像普通对象值一样。因此:

Access-O (1)
附加-分摊 O (1)(有时需要调整散列表的大小; 通常只需要插入)
通过 unshift预置 -O (n) ，因为它需要重新分配所有索引
Insertion - Amortized O(1) if the value does not exist. O(n) if you want to shift existing values (Eg, using splice).
删除-分摊 O (1)去除一个值，O (n)如果你想通过 splice重新分配索引。
交换 -O (1)

In general, setting or unsetting any key in a dict is amortized O(1), and the same goes for arrays, regardless of what the index is. Any operation that requires renumbering existing values is O(n) simply because you have to update all the affected values.