JavaScript数组的大O.

Question

通过添加和删除项目,可以非常轻松地修改JavaScript中的数组.它有点掩盖了大多数语言数组是固定大小的事实,并且需要复杂的操作来调整大小.似乎JavaScript可以很容易地编写性能不佳的数组代码.这导致了一个问题:

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

我假设所有合理的JavaScript实现至少具有以下大O.

• 访问 - 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)将是这两者的平均情况.

对于某些事情,我可以期待比我的假设更好的表现吗？我不希望在任何规范中概述任何内容,但实际上可能是所有主要实现都在后台使用优化的数组.是否有动态扩展阵列或其他一些性能提升算法？

PS

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

Answer 1

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

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

通常,在dict中设置或取消设置任何键是分摊O(1),对于数组也是如此,无论索引是什么.任何需要重新编号现有值的操作都是O(n),因为您必须更新所有受影响的值.

Answer 2

保证

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

现实

例如，V8（截至目前）使用哈希表和数组列表来表示数组。它还对对象有各种不同的表示形式，因此数组和对象无法进行比较。因此，数组访问始终优于 O(n)，甚至可能与 C++ 数组访问一样快。追加的时间复杂度为 O(1)，除非达到数据结构的大小并且必须对其进行缩放（即 O(n)）。预置更糟糕。如果您执行类似delete array[index]（不要！）的操作，删除可能会更糟，因为这可能会迫使引擎更改其表示形式。

建议

使用数组作为数值数据结构。这就是它们的目的。这就是引擎将优化它们的原因。避免稀疏数组（或者如果必须的话，性能会更差）。避免使用混合数据类型的数组（因为这会使内部表示更加复杂）。

如果您确实想针对某个引擎（和版本）进行优化，请检查其源代码以获得绝对答案。