Array.push与Array.unshift的性能

Question

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

• ECMAScript规范没有规定特定的运行时复杂性,因此它取决于具体的实现/ JavaScript引擎/运行时行为[1] [2].
• Array.push()运行在恒定和Array.unshift()在直线通过像数据结构的哈希表来实现稀疏数组时间[3] .

现在,我在想是否push和unshift对相同的恒定分别线性时间复杂度密集阵列.Firefox/Spidermonkey的实验结果证实:

现在我的问题:

• 是否有官方文档或参考资料确认观察到的Firefox/Spidermonkey和Chrome/Node/V8的运行时性能？
• 为什么unshift没有用类似的常量运行时实现push(例如维护索引偏移;类似于perl数组)？

Answer 1

要理解这一点,需要了解一下堆栈(在JavaScript,数组中)是如何在计算机科学中设计的,并且在RAM /内存中表示.如果你创建一个堆栈(一个数组),基本上你告诉系统在内存中为一个最终可以增长的堆栈分配一个空间.

现在,每次添加到该堆栈(带push)时,它都会添加到该堆栈的末尾.最终系统看到Stack不够大,所以它在oldstack.length*1.5-1中在内存中分配一个新空间,并将旧信息复制到新空间.这就是图表中跳跃/抖动的原因,否则看起来是扁平/线性的.此行为也是您始终应该使用预定义大小(如果您知道)初始化阵列/堆栈的原因,var a=new Array(1000)以便系统不需要"新分配内存并复制".

考虑到unshift,它似乎与推送非常相似.它只是将它添加到列表的开头,对吧？但是这种差异似乎不屑一顾,它非常大!正如push所解释的那样,当大小耗尽时,最终会有"分配内存并复制".通过unshift,它想要在开始时添加一些东西.但那里已经有了一些东西.因此,它必须将位置N处的元素移动到位置N + 1,N1到N1 + 1,N2到N2 + 1等.因为这是非常低效的,它实际上只是新分配内存,添加新元素然后复制在oldstack到newstack.这就是你的图形具有更多二次或甚至略微指数外观的原因.

总结;

• push添加到最后,很少需要重新分配内存+复制.

• unshift添加到开始并始终需要重新分配内存和复制数据

/编辑:关于你的问题为什么用"移动索引"没有解决这个问题当你使用unshift并且可以互换推送时,你需要多个"移动索引"和密集计算来确定索引2处元素的实际位置留在记忆中.但Stack背后的想法是具有O(1)复杂性.

还有许多其他数据结构具有这些属性(和更多功能),但需要权衡速度,内存使用情况等.其中一些数据结构是Vector,a Double-Linked-List,SkipList甚至是Binary Search Tree根据您的要求

这是一个很好的资源,解释数据结构和它们之间的一些差异/进步