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

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;
}

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];

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.

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.

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]

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
*/

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

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]

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]

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.