Javascript中unshift()与push()的时间复杂度

Question

我知道Javascript中的unshift()和push()方法有什么区别,但我想知道时间复杂度有什么不同？

我想push()方法是O(1),因为你只是在数组末尾添加一个项目,但我不确定unshift()方法,因为,我想你必须"移动"所有其他现有的元素向前,我想是O(log n)或O(n)？

Answer 1

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

Answer 2

据我所知,JavaScript语言规范并没有强制要求这些函数的时间复杂度.

当然可以用O(1)push和unshift操作实现类似数组的数据结构(O(1)随机访问).C++ std::deque就是一个例子.因此,使用C++ deques在内部表示Javascript数组的Javascript实现将具有O(1)push和unshift操作.

但是如果你需要保证这样的时间限制,你将不得不自己动手,如下所示:

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

Answer 3

是的你是对的。默认复杂度为push()O(1)，unshift()O(n)。因为unshift()必须增加数组中已存在的所有元素。但是，push()必须在数组末尾插入一个元素，因此数组元素的索引都不必更改。但是，push()由于内存的动态分配，也可以用 O(n) 的复杂度来表示。在javascript中，当您创建一个新数组而不指定所需的大小时，它将创建一个默认值的数组。在填充默认大小之前，推送操作的复杂度为 O(1)。但是，如果默认大小已满，编译器必须创建一个新的连续内存块，其大小是默认内存的两倍，并将已存在的元素复制到新分配的内存中。因此，将元素从一个连续内存块移动到另一个连续内存块需要 O(n) 时间。

如果您知道要放入数组中的元素数量，则可以避免插入元素时的复杂度为 O(n)。

1. 使用所需的大小初始化数组，并用虚拟值填充它。 let array = new Array(size).fill(0)
2. 迭代您想要推送的元素并按其索引更改值。

for (let i = 0; i < size; i++) {
  array[i] = i
}

因此，push()我们没有改变元素所在位置的索引。与创建具有默认值的数组并将元素推送到其中相比，它的内存效率更高，而且更简单。由于我们只使用了所需的内存量，因此不会浪费额外的内存。

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）（将根据元素数量线性缩放），但是如果我错了，请有人纠正我。