我在阅读有关数组操作的运行时复杂性的文章时了解到...
- ECMAScript 规范不要求特定的运行时复杂性，因此它取决于特定的实现/JavaScript 引擎/运行时行为 [1] [2] .
Array.push()以常数 和Array.unshift()以线性 时间运行，用于稀疏由类似哈希表的数据结构实现的数组 [3] .
现在我想知道 push 和 unshift 在 dense arrays 上是否具有相同的常数和线性时间复杂度. Firefox/Spidermonkey 中的实验结果证实:
现在我的问题:
- 是否有官方文档或引用资料证实观察到的 Firefox/Spidermonkey 和 Chrome/Node/V8 的运行时性能？
- 为什么
unshift没有使用类似于push的constant 运行时实现(例如保持索引偏移量；类似于 perl arrays ) ？
最佳答案
要理解这一点，需要了解堆栈(在 JavaScript 中为数组)在计算机科学中是如何设计的，以及如何在您的 RAM/内存中表示的。如果您创建一个堆栈(一个数组)，本质上您是在告诉系统在内存中为一个最终可以增长的堆栈分配一个空间。
现在，每次您添加到该堆栈(使用 push)时，它都会添加到该堆栈的end。最终系统发现 Stack 不够大，所以它在内存中分配了一个新空间 oldstack.length*1.5-1 并将旧信息复制到新空间。这就是你的图表中跳跃/抖动的原因，否则看起来平坦/线性。这种行为也是为什么你总是应该用 var a=new Array(1000) 初始化一个预定义大小(如果你知道)的数组/堆栈，这样系统就不需要“新分配内存并复制过来”。
考虑到unshift，它看起来和push很相似。它只是将它添加到列表的开始，对吗？但是，尽管这种差异看起来不屑一顾，但它非常大!正如推送所解释的那样，当大小用完时，最终会有一个“分配内存并复制”。对于 unshift，它希望向 start 添加一些内容。但是那里已经有东西了。所以它必须将位置 N 的元素移动到位置 N+1，N1 到 N1+1，N2 到 N2 +1 等。因为效率很低，它实际上只是重新分配内存，添加新元素，然后将旧堆栈复制到新堆栈。这就是您的图表看起来更像是二次方甚至是轻微指数的原因。
总结;
push添加到end，很少需要重新分配内存+复制。unshift添加到start 并且总是 需要重新分配内存并复制数据
/edit:关于你的问题为什么不能用“移动索引”解决这个问题是当你交替使用 unshift 和 push 时的问题，你需要多个“移动索引”和密集计算来找出那个元素在哪里索引 2 实际上驻留在内存中。但 Stack 背后的想法是具有 O(1) 的复杂性。
还有许多其他数据结构具有此类属性(和更多功能)，但在速度、内存使用等方面有所折衷。其中一些数据结构是 Vector，Double-Linked -List、SkipList 甚至是 Binary Search Tree，具体取决于您的要求
Here is a good resource explaining datastructures and some differences/advancements between them
关于javascript - Array.push 与 Array.unshift 的性能对比，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44031591/