JavaScript 数组的大 O

javascript arrays algorithm time-complexity big-o

2022-08-30 05:04:24

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

在数组性能方面，我可以期望JavaScript实现有什么性能（就O时间复杂性而言）？

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

交通 - O（1）
追加 - O（n）
预置 - O（n）
插入 - O（n）
删除 - O（n）
交换 - O（1）

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

我能指望某些事情的性能比我在这里的假设更好吗？我不期望任何规范中都概述任何内容，但在实践中，可能是所有主要实现都在幕后使用优化的数组。是否有动态扩展的阵列或其他一些性能提升的算法在起作用？

附言

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

答案 1

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

与大多数语言相比，它们使用数组实现数组，在Javascript数组中是对象，值存储在哈希表中，就像常规对象值一样。因此：

交通 - O（1）
追加 - 摊销 O（1）（有时需要调整哈希表的大小;通常只需要插入）
在前面 - O（n） via ，因为它需要重新分配所有索引unshift
插入 - 摊销 O（1），如果该值不存在。O（n）如果要移动现有值（例如，使用）。splice
删除 - 摊销 O（1）以删除值，如果要通过重新分配索引，则 O（n）splice
交换 - O（1）

通常，设置或取消设置字典中的任何键都是摊销的 O（1），数组也是如此，无论索引是什么。任何需要对现有值重新编号的操作都是 O（n），因为您必须更新所有受影响的值。

答案 2

保证

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

现实

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

建议

将数组用于数值数据结构。这就是它们的意义所在。这就是引擎将优化它们的原因。避免稀疏数组（或者，如果必须这样做，则期望性能更差）。避免使用具有混合数据类型的数组（因为这会使内部表示形式更加复杂）。

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