时间不印字（）与在Javascript推（）的复杂性(time complexity of unsh

我知道是什么的Javascript的unshift（）和推（）方法的区别，但我不知道是在什么时间复杂度的区别？

我想对push（）方法是O（1），因为你只是将项目添加到数组的结尾，但我不知道对不印字（）方法，因为，我想你必须“动”所有其他现有元件向前和我假设为O（log n）的或为O（n）？

Answer 1:

JavaScript语言规范没有强制要求这些功能的时间复杂度，因为据我所知。

这当然是可能实现具有O（1）的阵列状的数据结构（O（1）随机接入） push和unshift操作。在C ++ std::deque是一个例子。因此所使用C ++双端在内部表示的Javascript阵列A Javascript实现将具有O（1） push和unshift操作。

但是，如果你需要保证这样的时间界限，你将不得不推出自己的，就像这样：

http://code.stephenmorley.org/javascript/queues/

Answer 2:

推（）更快。

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

Answer 3:

恕我直言，这取决于JavaScript的引擎......如果它会使用一个链表，不印字应该是相当便宜...

Answer 4:

对于人们好奇的V8执行这里是源。因为unshift需要的参数的任意数量，阵列将转向本身以容纳所有参数。

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);

它需要的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);
    }
  }

我也想呼吁的是，V8拥有不同的概念element kinds取决于什么数组包含。这也可能会影响性能。

很难居然说表现是什么，因为如实这取决于传递什么类型的元素，有多少孔阵列中，等等。如果我通过这次更深入，也许我可以给一个明确的答案，但总的来说，我认为因为unshift需要在阵列中分配更多的空间，通常你还挺假设它是O（N）（将规模linerally取决于元素的数量），但有人请纠正我，如果我错了。