Временная сложность unshift() против push() в Javascript

Я знаю, в чем разница между методами unshift() и push() в Javascript, но мне интересно, какая разница во временной сложности?

Я полагаю, что метод push() - это O (1), потому что вы просто добавляете элемент в конец массива, но я не уверен в методе unshift(), потому что, полагаю, вам нужно "переместить", все остальные существующие элементы вперед, и я полагаю, что это O (log n) или O (n)?

Ответы

Ответ 1

Спецификация языка JavaScript не определяет временную сложность этих функций, насколько мне известно.

Конечно, возможно реализовать подобную массиву структуру данных (O (1) произвольный доступ) с операциями O (1) push и unshift. Пример С++ std::deque. Таким образом, реализация Javascript, использующая С++-требования для представления массивов Javascript внутри, должна иметь операции O (1) push и unshift.

Но если вам нужно гарантировать такие временные рамки, вам придется катиться самостоятельно, например:

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

Ответ 2

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

Ответ 3

imho это зависит от javascript-engine... если он будет использовать связанный список, unshift должен быть довольно дешевым...

Ответ 4

Один из способов реализации массивов с быстрым отключением и нажатием - просто поместить ваши данные в середину вашего массива уровня C. Это как perl делает это, IIRC.

Другой способ сделать это - иметь два отдельных массива уровня C, так что push присоединяется к одному из них, а unshift - к другому. Нет никакой реальной выгоды для этого подхода по сравнению с предыдущим, о котором я знаю.

Независимо от того, как это реализовано, push или или unshift будет занимать время O (1), когда внутренний массив C-уровня имеет достаточную запасную память, в противном случае при перераспределении необходимо выполнить хотя бы O (N) время для копирования старые данные в новый блок памяти.

Ответ 5

Для людей, интересующихся реализацией v8, вот источник. Поскольку unshift принимает произвольное количество аргументов, массив сместится сам, чтобы вместить все аргументы.

UnshiftImpl конечном итоге вызывает AddArguments с start_position AT_START которая 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) (будет линейно масштабироваться в зависимости от количества элементов), но кто-то, пожалуйста, исправьте меня, если я ошибаюсь.