JavaScript 数组的大 O [英] Big O of JavaScript arrays

问题描述

JavaScript 中的数组很容易通过添加和删除项目来修改.它在某种程度上掩盖了大多数语言数组是固定大小的事实，并且需要复杂的操作来调整大小.似乎 JavaScript 使得编写性能不佳的数组代码变得容易.这就引出了一个问题:

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:

在数组性能方面，我可以从 JavaScript 实现中获得什么性能(就大 O 时间复杂度而言)?

我假设所有合理的 JavaScript 实现最多有以下大 O.

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

• 访问 - O(1)
• 附加 - O(n)
• 前置 - O(n)
• 插入 - O(n)
• 删除 - O(n)
• 交换 - O(1)

JavaScript 允许您使用 new Array(length) 语法将数组预填充到特定大小.(额外问题:以这种方式创建数组是 O(1) 还是 O(n)) 这更像是一个传统数组，如果用作预先调整大小的数组，可以允许 O(1) 追加.如果添加循环缓冲区逻辑，则可以实现 O(1) 前置.如果使用动态扩展数组，则 O(log n) 将是两者的平均情况.

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?

附言

我想知道这一点的原因是我正在研究一些排序算法，其中大多数似乎在描述它们的整体大 O 时假设追加和删除是 O(1) 操作.

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.

推荐答案

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

与大多数使用数组实现数组的语言相比，Javascript 中的数组是对象，并且值存储在哈希表中，就像常规对象值一样.因此:

In contrast to most languages, which implement arrays with, well, arrays, in Javascript Arrays are objects, and values are stored in a hashtable, just like regular object values. As such:

• 访问 - O(1)
• 附加 - 摊销 O(1)(有时需要调整哈希表的大小；通常只需要插入)
• Prepending - O(n) 通过 unshift，因为它需要重新分配所有索引
• 插入 - 如果该值不存在，则摊销 O(1).O(n) 如果您想移动现有值(例如，使用 splice).
• 删除 - 分摊 O(1) 以删除值，O(n) 如果您想通过 splice 重新分配索引.
• 交换 - O(1)

• Access - O(1)
• Appending - Amortized O(1) (sometimes resizing the hashtable is required; usually only insertion is required)
• Prepending - O(n) via unshift, since it requires reassigning all the indexes
• Insertion - Amortized O(1) if the value does not exist. O(n) if you want to shift existing values (Eg, using splice).
• Deletion - Amortized O(1) to remove a value, O(n) if you want to reassign indices via splice.
• Swapping - O(1)

一般来说，设置或取消设置字典中的任何键的分摊时间为 O(1)，对于数组也是如此，无论索引是什么.任何需要对现有值重新编号的操作都是 O(n)，因为您必须更新所有受影响的值.

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.

这篇关于JavaScript 数组的大 O的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！