Array.push与Array.unshift的性能比较

Question

我正在阅读有关数组操作的运行时复杂度，并了解到...

• ECMAScript规范没有规定特定的运行时复杂度，因此它取决于具体的实现/ JavaScript引擎/运行时行为[1] [2]。
• Array.push()在由类似哈希表的数据结构实现的稀疏数组中以常数时间运行，而Array.unshift()则以线性时间运行[3]。

现在我想知道在dense arrays上，push和unshift是否具有相同的常数或线性时间复杂度。Firefox/Spidermonkey的实验结果证实了这一点：

现在我的问题:

• 是否有官方文档或参考资料证实了Firefox/Spidermonkey和Chrome/Node/V8的运行时性能？
• 为什么unshift没有像push一样实现常数运行时（例如维护索引偏移量；类似于perl数组）？

- le_m

---

请问以下内容与编程有关吗？https://dev59.com/fWct5IYBdhLWcg3wNq-v - Louis Loudog Trottier

@LouisLoudogTrottier 这是上面链接的问题之一，供参考。我的问题特定于所选实现，而不是规范要求的时间复杂度（即无）。 - le_m

Answer 1

为了理解这个问题，需要对计算机科学中栈的设计以及在RAM/内存中的表示有一定的了解。如果您创建一个栈（在JavaScript中是一个数组），本质上您是告诉系统为一个可能会增长的栈分配一定的内存空间。

每次向栈中添加元素（使用push），它被添加到栈的末尾。最终，系统发现栈不够大了，因此它会在旧的栈长度*1.5-1处分配新的内存空间，并将旧信息复制到新的空间。这就是push操作图表中出现跳跃和抖动的原因，否则看起来应该是平滑线性的。这种行为也是为什么您总是应该使用预定义大小（如果您知道）来初始化数组/栈（例如var a = new Array(1000)），这样系统就不需要“新分配内存并复制”了。

考虑unshift，它看起来非常类似于push。它只是将其添加到列表的开头，对吧？但是尽管这个区别看起来微不足道，实际上却非常重要！如push所述，当大小用尽时，最终会出现“分配内存并复制”的情况。使用unshift时，它想要添加到开头。但是那里已经有东西了。因此，它必须将位于位置N的元素移到位置N+1，以及将N1移到N1+1，N2移到N2+1等。由于这非常低效，实际上它只会新分配内存，添加新元素，然后将旧栈复制到新栈中。这就是为什么您的图表看起来更具有二次甚至略微指数型的原因。

总之：

• push操作会在末尾添加元素，并且很少需要重新分配内存和复制。

• unshift指的是在开头添加元素，但这样做总是需要重新分配内存并复制数据

/编辑：关于你为什么不能用“移动索引”解决问题的问题是，当你交替使用unshift和push时，你需要多个“移动索引”和密集的计算才能确定索引2处的元素实际上存在于哪个内存位置。但栈的思想是具有O（1）复杂度。

还有许多其他具有这些属性（及更多功能）的数据结构，但它们速度、内存使用等方面都有一定的折衷。其中一些数据结构是Vector、双向链表、SkipList，或者根据您的要求可能是二叉查找树

这里有一个很好的资源，介绍了一些数据结构以及它们之间的差异/进展

- japrescott

---

谢谢！这就是你的图表中出现跳动/抖动的原因 - 看起来是这样，但我想知道为什么这些抖动以某种恒定而非对数速率出现（例如与“步骤”进行比较）。可能与垃圾收集有关？因此，它将不得不将位置N处的元素移动到位置N + 1处 - 或者它可以增加一个索引偏移量，然后在通过它们的索引访问数组元素时添加（这就是我所说的“例如维护索引偏移量”的意思）。仍在寻找“为什么”和参考资料。 - le_m

关于你的第二个问题，请查看我更新的答案，了解其他数据结构。 至于你的第一个问题；抖动很可能与GC或其他在你的系统上运行的程序有关。正如你所看到的，它是非常恒定的增长，因此是线性的->更多元素->花费更多时间。对数意味着更多的元素->更少的时间。指数意味着更多的元素->更多的时间。 - japrescott

但是堆栈背后的想法是具有O(1)复杂度 - 也许我的解释太简短了；在两个方向上附加的O(1)复杂度是绝对可行的；例如与Perl数组perlmonks.org/?node_id=17890进行比较 - 关于抖动的问题；同意您的更新。大约2倍的增长因子会导致“步骤”，抖动可能与垃圾收集有关。感谢有价值的讨论！ - le_m

new Array(1000) 会引起其他问题，因为它创建了一个“带洞数组”，无法像没有洞的数组那样进行优化。如果您只创建数组一次但使用多次，则 push 可能仍然更快。另一个选项是使用 new Array(1000) 创建数组，然后在填充后使用 myArray = JSON.parse(JSON.stringify(myArray)) 进行复制，因为该副本将不会有洞。 - Yay295

一个常见的优化方法是，在使用unshift调用的循环算法时，改用Array.push，并在最后使用Array.reverse反转元素。 - Vincent Pazeller