Najbardziej wydajny sposób na dodanie wartości do tablicy

268

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;
}
samccone
źródło
tak jak uwielbiam połączone listy i wskaźniki, czuję, że musi istnieć bardziej skuteczny sposób na robienie rzeczy przy użyciu rodzimych typów danych JS
samccone
@samccone: Tak, zignoruj ​​mój komentarz przepraszam, myślałem, że powiedziałeś Java: P
GWW
3
Java, JavaScript, C lub Python, nie ma znaczenia w jakim języku: złożoność kompromisu między tablicami a połączonymi listami jest taka sama. Listy połączone są prawdopodobnie dość nieporęczne w JS, ponieważ nie ma dla nich wbudowanej klasy (w przeciwieństwie do Java), ale jeśli tak naprawdę chcesz czasu wstawiania O (1), to potrzebujesz listy połączonej.
mgiuca
1
Czy trzeba go sklonować?
Ryan Florence,
1
Jeśli konieczne jest jego sklonowanie, wówczas cofnięcie zmiany jest niewłaściwe, ponieważ spowoduje to mutację oryginalnej tablicy, a nie utworzenie kopii.
mgiuca

Odpowiedzi:

492

Nie jestem pewien, czy jest bardziej wydajny pod względem big-O, ale na pewno użycie tej unshiftmetody jest bardziej zwięzłe:

var a = [1, 2, 3, 4];
a.unshift(0);
a; // => [0, 1, 2, 3, 4]

[Edytować]

Ten test porównawczy jsPerf pokazuje, że unshiftjest 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:

a.slice().unshift(0); // Use "slice" to avoid mutating "a".

[Edytuj 2]

Dla kompletności można użyć następującej funkcji zamiast przykładu OP, prependArray(...)aby skorzystać z unshift(...)metody Array :

function prepend(value, array) {
  var newArray = array.slice();
  newArray.unshift(value);
  return newArray;
}

var x = [1, 2, 3];
var y = prepend(0, x);
y; // => [0, 1, 2, 3];
x; // => [1, 2, 3];
maerika
źródło
190
Kto zdecydował się zadzwonić prependunshift”?
Scott Stafford,
12
@ScottStafford unshiftwydaje się bardziej odpowiedni dla takiej operacji tablicowej (przenosi elementy ... mniej więcej fizycznie). prependbyłoby bardziej odpowiednie dla połączonych list, w których dosłownie dodajesz elementy.
CamilB,
12
unshift jest funkcją uzupełniającą do zmiany. Nazwanie go „prepend” byłoby dziwnym wyborem. Unshift ma się przesuwać, gdy popycha się, by pop.
Sir Robert
9
Tylko jeden problem z tym rozwiązaniem. Czy unshift () nie zwraca jego długości , a nie tablicy, jak w tej odpowiedzi? w3schools.com/jsref/jsref_unshift.asp
iDVB
4
pushi unshiftoba zawierają u, popa jednocześnie shiftnie mają.
Qian Chen,
70

Za pomocą ES6 możesz teraz użyć operatora rozkładania, aby utworzyć nową tablicę z nowymi elementami wstawionymi przed elementami oryginalnymi.

// Prepend a single item.
const a = [1, 2, 3];
console.log([0, ...a]);

// Prepend an array.
const a = [2, 3];
const b = [0, 1];
console.log([...b, ...a]);

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.

Frank Tan
źródło
4
Powinno to zostać poddane pod głosowanie od 2017 r. Jest zwięzłe. Za pomocą spreadu zwraca nowy strumień, który może być przydatny do tworzenia kolejnych modyfikacji. Jest również czysty (co oznacza, że ​​nie ma to wpływu na aib)
Simon
Nie wspominałeś już o czasochłonności w porównaniu dounshift
Shashank Vivek
Dzięki @ShashankVivek. Chciałem, aby ta odpowiedź przedstawiła alternatywną składnię, która moim zdaniem jest bardziej niezapomniana i zwięzła. Zaktualizuję.
Frank Tan,
@FrankTan: Na zdrowie :) +1
Shashank Vivek
46

Jeśli przygotowujesz tablicę do przodu innej tablicy, bardziej wydajne jest jej użycie concat. Więc:

var newArray = values.concat(oldArray);

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.

mgiuca
źródło
2
O tak, zapomniałem o unshift. Zauważ jednak, że a) mutuje oldArray, podczas concatgdy nie (to, który z nich jest lepszy, zależy od sytuacji), i b) wstawia tylko jeden element.
mgiuca
1
Wow, to jest znacznie wolniejsze. Cóż, jak powiedziałem, robi kopię tablicy (a także tworzy nową tablicę [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.
mgiuca
2
jest dobry dla onelinera, ponieważ concat zwraca tablicę, a unshift zwraca nową długość
Z. Khullah
32

Jeśli chcesz dodać tablicę (a1 z tablicą a2), możesz użyć:

var a1 = [1, 2];
var a2 = [3, 4];
Array.prototype.unshift.apply(a1, a2);
console.log(a1);
// => [3, 4, 1, 2]
uroslaty
źródło
6

f musisz zachować starą tablicę, wytnij starą i przenieś nowe wartości na początek wycinka.

var oldA=[4,5,6];
newA=oldA.slice(0);
newA.unshift(1,2,3)

oldA+'\n'+newA

/*  returned value:
4,5,6
1,2,3,4,5,6
*/
Kennebec
źródło
4

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

John Klimov
źródło
Świetna odpowiedź! Ale aby upewnić się, że nie stracisz części, możesz odtworzyć tutaj swoje przypadki testowe (być może z kilkoma przykładowymi wynikami testów) na wypadek, gdyby np. Jsbench zniknął.
ruffin
3

Istnieje specjalna metoda:

a.unshift(value);

Ale jeśli chcesz dodać kilka elementów do tablicy, szybsze byłoby użycie takiej metody:

var a = [1, 2, 3],
    b = [4, 5];

function prependArray(a, b) {
    var args = b;
    args.unshift(0);
    args.unshift(0);
    Array.prototype.splice.apply(a, args);
}

prependArray(a, b);
console.log(a); // -> [4, 5, 1, 2, 3]
Bjornd
źródło
2
Nie ... unshift doda tablicę jako pierwszy argument: var a = [4, 5]; a. przesunięcie ([1,2,3]); console.log (a); // -> [[4, 5], 1, 2, 3]
bjornd
4
Masz rację! Trzeba by było użyćArray.prototype.unshift.apply(a,b);
David
1

Przykład wstępnego przygotowania w miejscu:

var A = [7,8,9]
var B = [1,2,3]

A.unshift(...B)

console.log(A) // [1,2,3,7,8,9]

Miguel Mota
źródło
1

Wywołanie unshiftzwraca tylko długość nowej tablicy. Aby dodać element na początku i zwrócić nową tablicę, zrobiłem to:

let newVal = 'someValue';
let array = ['hello', 'world'];
[ newVal ].concat(array);

lub po prostu z operatorem rozprzestrzeniania:

[ newVal, ...array ]

W ten sposób pierwotna tablica pozostaje nietknięta.

rehman_00001
źródło