Array.push与Array.unshift的性能 [英] Performance of Array.push vs Array.unshift

问题描述

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

I was reading about runtime complexities of array operations and learned that...

• ECMAScript规范没有规定特定的运行时复杂性，因此它取决于特定的实现/JavaScript引擎/运行时行为 [2] .
对于由哈希表(如数据结构[3] .

• the ECMAScript specification does not mandate a specific runtime complexity, so it depends on the specific implementation / JavaScript engine / runtime behavior [1] [2].
• Array.push() runs in constant andArray.unshift() in linear time for sparse arrays implemented by a hash-table like data structure [3].

现在，我想知道push和unshift在

Now I was left wondering whether push and unshift have the same constant respectively linear time complexity on dense arrays. Experimental results in Firefox/Spidermonkey confirm that:

现在我的问题:

• 是否有官方文档或参考文献确认了Firefox/Spidermonkey和Chrome/Node/V8的观察到的运行时性能?
• 为什么未使用类似于push的恒定运行时实现unshift(例如，维护索引偏移量；类似于

• Are there official docs or references confirming the observed runtime performance for Firefox/Spidermonkey and Chrome/Node/V8?
• Why has unshift not been implemented with constant runtime similar to push (and e.g. maintaining an index offset; similar to perl arrays)?

推荐答案

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

to understand this, there needs to be some knowledge about how a Stack (in JavaScript, an Array) is designed in computer science and is represented within your RAM/memory. If you create a Stack(an Array), essentially you are telling the system to allocate a space in memory for a stack that eventually can grow.

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

Now, everytime you add to that Stack (with push), it adds to the end of that stack. Eventually the system sees that the Stack isn't going to be big enough, so it allocates a new space in memory at oldstack.length*1.5-1 and copies the old information to the new space. This is the reason for the jumps/jitters in your graph for push that otherwise look flat/linear. This behavior is also the reason why you always should initialize an Array/Stack with a predefined size (if you know it) with var a=new Array(1000) so that the system doesn't need to "newly allocate memory and copy over".

考虑unshift，它看起来与推非常相似.它只是将其添加到列表的开始，对吗?但是，看起来这种差异似乎令人不屑一顾，其差异非常大！如推的解释，当大小用完时，最终会出现分配内存并复制"的情况.取消移位后，它想在开始中添加一些内容.但是已经有东西了.因此，必须将元素移动到位置 N 到位置 N + 1 ， N1到N1 + 1 ， N2到N2 +1 等.因为这效率很低，所以它实际上只是重新分配内存，添加新的Element，然后通过旧堆栈复制到新堆栈.这就是您的图形具有二次方甚至指数级外观的原因.

Considering unshift, it seems very similar to push. It just adds it to the start of the list, right? But as dismissive this difference seems, its very big! As explained with push, eventually there is a "allocate memory and copy over" when size runs out. With unshift, it wants to add something to the start. But there is already something there. So it would have to move the element at position N to position N+1, N1 to N1+1, N2 to N2+1 etc. Because that is very inefficient, it actually just newly allocates memory, adds the new Element and then copies over the oldstack to the newstack. This is the reason your graph has more an quadratic or even a slight exponential look to it.

总结；

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

• push adds to the end and rarely needs reallocate memory+copy over.

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

unshift adds to the start and always needs to reallocate memory and copy data over

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

/edit: regarding your questions why this isn't solved with a "moving index" is the problem when you use unshift and push interchangeably, you would need multiple "moving indexes" and intensive computing to figure out where that element at index 2 actually resides in memory. But the idea behind a Stack is to have O(1) complexity.

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

There are many other datastructures that have such properties (and more features) but at a tradeoff for speed, memory usage, etc. Some of these datastructures are Vector, a Double-Linked-List, SkipList or even a Binary Search Tree depending on your requirements

这里是解释数据结构和某些方面的好资源他们之间的差异/进步

这篇关于Array.push与Array.unshift的性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！