Я знаю, в чем разница между методами unshift() и push() в Javascript, но мне интересно, какая разница во временной сложности?
Я полагаю, что метод push() - это O (1), потому что вы просто добавляете элемент в конец массива, но я не уверен в методе unshift(), потому что, полагаю, вам нужно "переместить", все остальные существующие элементы вперед, и я полагаю, что это O (log n) или O (n)?
Спецификация языка JavaScript не определяет временную сложность этих функций, насколько мне известно.
Конечно, возможно реализовать подобную массиву структуру данных (O (1) произвольный доступ) с операциями O (1) push и unshift. Пример С++ std::deque. Таким образом, реализация Javascript, использующая С++-требования для представления массивов Javascript внутри, должна иметь операции O (1) push и unshift.
Но если вам нужно гарантировать такие временные рамки, вам придется катиться самостоятельно, например:
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
imho это зависит от javascript-engine... если он будет использовать связанный список, unshift должен быть довольно дешевым...
Один из способов реализации массивов с быстрым отключением и нажатием - просто поместить ваши данные в середину вашего массива уровня C. Это как perl делает это, IIRC.
Другой способ сделать это - иметь два отдельных массива уровня C, так что push присоединяется к одному из них, а unshift - к другому. Нет никакой реальной выгоды для этого подхода по сравнению с предыдущим, о котором я знаю.
Независимо от того, как это реализовано, push или или unshift будет занимать время O (1), когда внутренний массив C-уровня имеет достаточную запасную память, в противном случае при перераспределении необходимо выполнить хотя бы O (N) время для копирования старые данные в новый блок памяти.
Для людей, интересующихся реализацией 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) (будет линейно масштабироваться в зависимости от количества элементов), но кто-то, пожалуйста, исправьте меня, если я ошибаюсь.