Zakładając, że mam tablicę o rozmiarze N
(gdzie N > 0
), czy istnieje bardziej skuteczny sposób dodawania do tablicy, który nie wymagałby kroków O (N + 1)?
W kodzie zasadniczo to, co obecnie robię
function prependArray(value, oldArray) {
var newArray = new Array(value);
for(var i = 0; i < oldArray.length; ++i) {
newArray.push(oldArray[i]);
}
return newArray;
}
javascript
arrays
prepend
samccone
źródło
źródło
Odpowiedzi:
Nie jestem pewien, czy jest bardziej wydajny pod względem big-O, ale na pewno użycie tej
unshift
metody jest bardziej zwięzłe:[Edytować]
Ten test porównawczy jsPerf pokazuje, że
unshift
jest przyzwoicie szybszy w co najmniej kilku przeglądarkach, niezależnie od możliwej różnej wydajności big-O, jeśli jesteś w stanie zmodyfikować tablicę na miejscu. Jeśli naprawdę nie możesz zmutować oryginalnej tablicy, możesz zrobić coś takiego jak poniższy fragment, który nie wydaje się być znacznie szybszy niż rozwiązanie:[Edytuj 2]
Dla kompletności można użyć następującej funkcji zamiast przykładu OP,
prependArray(...)
aby skorzystać zunshift(...)
metody Array :źródło
prepend
„unshift
”?unshift
wydaje się bardziej odpowiedni dla takiej operacji tablicowej (przenosi elementy ... mniej więcej fizycznie).prepend
byłoby bardziej odpowiednie dla połączonych list, w których dosłownie dodajesz elementy.push
iunshift
oba zawierająu
,pop
a jednocześnieshift
nie mają.Za pomocą ES6 możesz teraz użyć operatora rozkładania, aby utworzyć nową tablicę z nowymi elementami wstawionymi przed elementami oryginalnymi.
Aktualizacja 2018-08-17: Wydajność
Chciałem, aby ta odpowiedź przedstawiła alternatywną składnię, która moim zdaniem jest bardziej niezapomniana i zwięzła. Należy zauważyć, że zgodnie z niektórymi testami porównawczymi (patrz inna odpowiedź ), ta składnia jest znacznie wolniejsza. Prawdopodobnie nie będzie to miało znaczenia, chyba że wykonasz wiele z tych operacji w pętli.
źródło
unshift
Jeśli przygotowujesz tablicę do przodu innej tablicy, bardziej wydajne jest jej użycie
concat
. Więc:Ale nadal będzie to O (N) wielkości oldArray. Mimo to jest bardziej wydajny niż ręczne iterowanie po oldArray. Ponadto, w zależności od szczegółów, może ci to pomóc, ponieważ jeśli zamierzasz dodać wiele wartości, lepiej najpierw umieścić je w tablicy, a następnie na końcu skonfatować oldArray, zamiast przygotowywać każdą z osobna.
Nie ma lepszego sposobu niż O (N) w rozmiarze oldArray, ponieważ tablice są przechowywane w ciągłej pamięci z pierwszym elementem w ustalonej pozycji. Jeśli chcesz wstawić przed pierwszym elementem, musisz przenieść wszystkie pozostałe elementy. Jeśli potrzebujesz obejść ten problem, zrób to, co powiedział @GWW i użyj połączonej listy lub innej struktury danych.
źródło
unshift
. Zauważ jednak, że a) mutuje oldArray, podczasconcat
gdy nie (to, który z nich jest lepszy, zależy od sytuacji), i b) wstawia tylko jeden element.[0]
), podczas gdy unshift mutuje ją w miejscu. Ale oba powinny być O (N). Pozdrawiam również link do tej strony - wygląda bardzo przydatnie.Jeśli chcesz dodać tablicę (a1 z tablicą a2), możesz użyć:
źródło
f musisz zachować starą tablicę, wytnij starą i przenieś nowe wartości na początek wycinka.
źródło
Mam kilka świeżych testów różnych metod przygotowywania. W przypadku małych tablic (<1000 elementów) lider jest dla cyklu sprzężonego z metodą push. W przypadku dużych tablic metoda Unshift staje się liderem.
Ale ta sytuacja dotyczy tylko przeglądarki Chrome. W Firefoksie unshift ma niesamowitą optymalizację i jest szybszy we wszystkich przypadkach.
ES6 rozprzestrzenia się ponad 100 razy wolniej we wszystkich przeglądarkach.
https://jsbench.me/cgjfc79bgx/1
źródło
Istnieje specjalna metoda:
Ale jeśli chcesz dodać kilka elementów do tablicy, szybsze byłoby użycie takiej metody:
źródło
Array.prototype.unshift.apply(a,b);
Przykład wstępnego przygotowania w miejscu:
źródło
Wywołanie
unshift
zwraca tylko długość nowej tablicy. Aby dodać element na początku i zwrócić nową tablicę, zrobiłem to:lub po prostu z operatorem rozprzestrzeniania:
W ten sposób pierwotna tablica pozostaje nietknięta.
źródło