Performance of Array.push vs Array.unshift 性能比较
Performance of Array.push vs Array.unshift 性能比较
我在阅读有关数组操作的运行时复杂度时了解到...
- ECMAScript规范没有规定特定的运行时复杂度，它取决于具体的实现/JavaScript引擎/运行时行为[1] [2]。
Array.push()对于由哈希表类似的数据结构实现的稀疏数组具有常数时间复杂度，而Array.unshift()具有线性时间复杂度[3]。
现在我想知道在密集数组上，push和unshift是否具有相同的常数和线性时间复杂度。Firefox/Spidermonkey的实验结果证实了这一点：
现在我的问题是：
- 是否有官方文档或参考资料证实了Firefox/Spidermonkey和Chrome/Node/V8的观察到的运行时性能？
- 为什么
unshift没有像push一样实现常数运行时复杂度（例如保持索引偏移，类似于perl数组）？
数组的push和unshift方法都是用来向数组中添加元素的。然而，它们的性能却有所不同。本文将探讨push和unshift方法的性能差异产生的原因，并提供一些解决方法。
首先，需要了解计算机科学中栈（在JavaScript中即为数组）的设计方式以及在RAM/内存中的表示方式。当你创建一个栈（数组）时，实际上是告诉系统为栈分配一块内存空间，以便栈能够不断增长。
每次使用push方法向栈中添加元素时，它会将元素添加到栈的末尾。当栈的大小不够时，系统会分配一块新的内存空间，大小为旧栈长度的1.5倍减1，并将旧数据复制到新的空间中。这就是push方法在图表中出现跳跃/抖动的原因，尽管在图表上看起来是平坦/线性的。这种行为也是为什么应该始终使用预定义大小（如果已知）来初始化数组/栈的原因，例如var a = new Array(1000)，这样系统就不需要“重新分配内存并复制数据”。
相比之下，unshift方法看起来与push方法非常相似，只是将元素添加到列表的开头而已。但是，尽管这个区别看起来不太重要，但实际上差别很大！正如之前解释的，当大小不够时，push方法会进行“重新分配内存并复制数据”，而unshift方法想要将元素添加到开头。但是，开头已经有元素了。所以它需要将位置N的元素移动到位置N+1，位置N1的元素移动到位置N1+1，位置N2的元素移动到位置N2+1等等。由于这样做非常低效，实际上unshift方法会重新分配内存，添加新元素，然后将旧栈复制到新栈中。这就是为什么图表呈现出二次或稍微呈指数增长的原因。
综上所述：
- push方法将元素添加到末尾，很少需要重新分配内存和复制数据。
- unshift方法将元素添加到开头，始终需要重新分配内存和复制数据。
关于你提出的问题，为什么不能使用“移动索引”的解决方法，是因为当你交替使用unshift和push方法时，你需要多个“移动索引”并进行大量计算，以确定索引为2的元素实际在内存中的位置。但是栈的设计理念是具有O(1)的复杂度。
除了数组，还有许多其他具有类似性质（以及更多功能）的数据结构，但它们在速度、内存使用等方面存在折衷。一些这样的数据结构包括Vector、双向链表、跳表或者根据需求选择的二叉搜索树。
在使用unshift方法进行循环算法时，一种常见的优化方法是改用push方法，并在最后使用Array.reverse方法将元素顺序反转。
其他一些解决方法包括使用.splice(0,0,element)代替unshift方法，以及使用amortized analysis（摊还分析）的方法来解释.push方法性能的波动。
总之，push方法通常是快速的，但有时会变慢，而unshift方法的性能始终较差。在选择使用哪种方法时，需要根据具体需求考虑性能和内存的权衡。