javascript - Array.push与Array.unshift的性能

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

ECMAScript规范并不要求特定的运行时复杂性，因此它取决于特定的实现/JavaScript引擎/运行时行为[1] [2]。

Array.push()在常量和Array.unshift()中以线性时间运行，用于由哈希表(如数据结构[3])实现的稀疏数组。

现在我想知道push和unshift在dense arrays上是否分别具有相同的常数线性时间复杂度。 Firefox/Spidermonkey中的实验结果证实:



现在我的问题:

是否有官方文档或引用资料确认Firefox/Spidermonkey和Chrome/Node/V8的运行时性能？

为什么未使用类似于unshift的常量运行时来实现push(例如，维护索引偏移量；类似于perl arrays)？

最佳答案

要理解这一点，需要对计算机科学中堆栈(在JavaScript中为数组)的设计方式以及如何在您的RAM/内存中表示的知识。如果创建一个堆栈(一个数组)，则实际上是在告诉系统在内存中为最终可以增长的堆栈分配空间。

现在，每次您添加到该堆栈(带有push)时，它都会添加到该堆栈的端。最终，系统发现堆栈不够大，因此它在oldstack.length * 1.5-1的内存中分配了一个新空间，并将旧信息复制到新空间。这就是图形中插入的跳跃/抖动看起来不平坦/线性的原因。这也是为什么您始终应使用var a=new Array(1000)初始化具有预定义大小(如果知道)的Array/Stack的原因，因此系统不需要“新分配内存并复制”。

考虑到unshift，似乎与push非常相似。它只是将其添加到列表的开始中，对吗？但是，看起来这种差异似乎令人不屑一顾，其差异很大!如推的解释，当大小用完时，最终会有一个“分配内存并复制”。使用unshift时，它想向 start 添加一些内容。但是已经有东西了。因此，它必须将元素在位置N移到位置N + 1，从N1移至N1 + 1，从N2移至N2 + 1，等等。由于效率很低，它实际上只是重新分配内存，添加新元素，然后复制从旧堆栈到新堆栈。这就是您的图形具有二次方甚至指数级外观的原因。

总结

push添加到端，很少需要重新分配内存+复制。

unshift添加到中开始，并且始终需要重新分配内存并通过

复制数据

/edit:关于您的问题，为什么不能通过“移动索引”解决此问题，这是当您使用unshift并交替推送时的问题，您将需要多个“移动索引”和密集计算来找出索引2处的元素实际位于何处驻留在内存中。但是堆栈背后的想法是具有O(1)复杂性。

还有许多其他具有此类属性(和更多功能)的数据结构，但需要在速度，内存使用等方面进行权衡。根据您的要求，其中一些数据结构为Vector，Double-Linked-List，SkipList甚至是Binary Search Tree
Here is a good resource explaining datastructures and some differences/advancements between them