118

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

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

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

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

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

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

附言

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

4

2 回答 2

124

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

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

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

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

于 2012-07-18T06:01:59.867 回答
3

保证

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

现实

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

建议

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

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

于 2020-05-10T14:16:08.480 回答