Javascript 中 unshift() 与 push() 的时间复杂度
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12250697/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Time complexity of unshift() vs. push() in Javascript
提问by dperitch
I know what is the difference between unshift()and push()methods in JavaScript, but I'm wondering what is the difference in time complexity?
我知道JavaScript 中的unshift()和push()方法之间有什么区别，但我想知道时间复杂度有什么区别？
I suppose for push()method is O(1) because you're just adding an item to the end of array, but I'm not sure for unshift()method, because, I suppose you must "move" all the other existing elements forward and I suppose that is O(log n) or O(n)?
我想push()方法是 O(1) 因为你只是在数组的末尾添加一个项目，但我不确定unshift()方法，因为，我想你必须向前“移动”所有其他现有元素，我想那是 O(log n) 还是 O(n)？
采纳答案by Nemo
The JavaScript language spec does not mandate the time complexity of these functions, as far as I know.
据我所知，JavaScript 语言规范并没有强制要求这些函数的时间复杂度。
It is certainly possible to implement an array-like data structure (O(1) random access) with O(1) pushand unshiftoperations. The C++ std::dequeis an example. A Javascript implementation that used C++ deques to represent Javascript arrays internally would therefore have O(1) pushand unshiftoperations.
使用 O(1)push和unshift操作实现类数组数据结构（O(1) 随机访问）当然是可能的。C++std::deque就是一个例子。因此，使用 C++ 双端队列在内部表示 Javascript 数组的 Javascript 实现将具有 O(1)push和unshift操作。
But if you need to guarantee such time bounds, you will have to roll your own, like this:
但是，如果您需要保证这样的时间范围，则必须自己滚动，如下所示：
回答by Shanti
push() is faster.
push() 更快。
js>function foo() {a=[]; start = new Date; for (var i=0;i<100000;i++) a.unshift(1); return((new Date)-start)}
js>foo()
2190
js>function bar() {a=[]; start = new Date; for (var i=0;i<100000;i++) a.push(1); return((new Date)-start)}
js>bar()
10
回答by aug
For people curious about the v8 implementation here is the source. Because unshifttakes an arbitrary number of arguments, the array will shift itself to accommodate all arguments.
对于对 v8 实现感到好奇的人，这里是源代码。因为unshift接受任意数量的参数，数组将自行移动以容纳所有参数。
UnshiftImplends up calling AddArgumentswith a start_positionof AT_STARTwhich kicks it to this elsestatement
UnshiftImpl最终调用AddArguments了start_position的AT_START它踢这个else说法
// If the backing store has enough capacity and we add elements to the
// start we have to shift the existing objects.
Isolate* isolate = receiver->GetIsolate();
Subclass::MoveElements(isolate, receiver, backing_store, add_size, 0,
length, 0, 0);
and takes it to the MoveElements.
并将其带到MoveElements.
static void MoveElements(Isolate* isolate, Handle<JSArray> receiver,
Handle<FixedArrayBase> backing_store, int dst_index,
int src_index, int len, int hole_start,
int hole_end) {
Heap* heap = isolate->heap();
Handle<BackingStore> dst_elms = Handle<BackingStore>::cast(backing_store);
if (len > JSArray::kMaxCopyElements && dst_index == 0 &&
heap->CanMoveObjectStart(*dst_elms)) {
// Update all the copies of this backing_store handle.
*dst_elms.location() =
BackingStore::cast(heap->LeftTrimFixedArray(*dst_elms, src_index))
->ptr();
receiver->set_elements(*dst_elms);
// Adjust the hole offset as the array has been shrunk.
hole_end -= src_index;
DCHECK_LE(hole_start, backing_store->length());
DCHECK_LE(hole_end, backing_store->length());
} else if (len != 0) {
WriteBarrierMode mode = GetWriteBarrierMode(KindTraits::Kind);
dst_elms->MoveElements(heap, dst_index, src_index, len, mode);
}
if (hole_start != hole_end) {
dst_elms->FillWithHoles(hole_start, hole_end);
}
}
I also want to call out that v8 has a concept of different element kindsdepending what the array contains. This also can affect the performance.
我还想指出 v8 有一个不同的概念，element kinds具体取决于数组包含的内容。这也会影响性能。
It's hard to actually say what the performance is because truthfully it depends on what types of elements are passed, how many holes are in the array, etc. If I dig through this more, maybe I can give a definitive answer but in general I assume since unshiftneeds to allocate more space in the array, in general you can kinda assume it's O(N) (will scale linerally depending on the number of elements) but someone please correct me if I'm wrong.
实际上很难说出性能是什么，因为实际上它取决于传递的元素类型，数组中有多少个孔等等。如果我深入研究这个，也许我可以给出明确的答案，但总的来说我假设由于unshift需要在数组中分配更多空间，因此通常您可以假设它是 O(N)（将根据元素数量线性缩放），但如果我错了，请有人纠正我。
回答by BenGoldberg
One way of implementing Arrays with both fast unshift and push is to simply put your data into the middle of your C-level array. That's how perl does it, IIRC.
使用快速 unshift 和 push 实现数组的一种方法是简单地将数据放入 C 级数组的中间。这就是 perl 的做法，IIRC。
Another way to do it is have two separate C-level arrays, so that push appends to one of them, and unshift appends to the other. There's no real benefit to this approach over the previous one, that I know of.
另一种方法是使用两个单独的 C 级数组，以便将 push 附加到其中一个，并将 unshift 附加到另一个。据我所知，与前一种方法相比，这种方法没有真正的好处。
Regardless of how it's implemented, a push or and unshift will take O(1) time when the internal C-level array has enough spare memory, otherwise, when reallocation must be done, at least O(N) time to copy the old data to the new block of memory.
不管它是如何实现的，当内部 C 级数组有足够的空闲内存时，push 或 unshift 将花费 O(1) 时间，否则，当必须进行重新分配时，至少需要 O(N) 时间来复制旧数据到新的内存块。
回答by TheHe
imho it depends on the javascript-engine... if it will use a linked list, unshift should be quite cheap...
恕我直言，这取决于 javascript 引擎……如果它将使用链表，则 unshift 应该很便宜……
