javascript - Mest effektiv måte å legge til en verdi foran i et array

Hvis jeg antar at jeg har et array som har en størrelse på N (der N > 0), finnes det en mer effektiv måte å legge til elementer foran arrayet på som ikke krever O(N + 1) operasjoner?

I kode gjør jeg essensielt det jeg gjør akkurat nå

function prependArray(value, oldArray) {
  var newArray = new Array(value);

  for(var i = 0; i < oldArray.length; ++i) {
    newArray.push(oldArray[i]);
  }

  return newArray;
}

Svar #1

Jeg er ikke sikker på om det er mer effektivt når det gjelder big-O, men det å bruke unshift-metoden er absolutt mer konsist:

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

[Rediger]

Denne jsPerf-benchmarken viser at unshift er ganske mye raskere i minst et par nettlesere, uavhengig av muligens forskjellig big-O-ytelse hvis du er ok med å endre arrayet på stedet. Hvis du virkelig ikke kan mutere det originale arrayet, ville du gjort noe som det nedenstående snippet, som ikke ser ut til å være merkbart raskere enn løsningen din:

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

[Rediger 2]

For fullstendighet kan følgende funksjon brukes i stedet for OPs eksempel prependArray(...) for å dra nytte av Array unshift(...)-metoden:

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

var x = [1, 2, 3];
var y = prepend(0, x);
// x => [1, 2, 3];
// y => [0, 1, 2, 3];
console.log({ x, y });

Svar #2

Med ES6 kan du nå bruke spreoperatoren for å lage et nytt array med dine nye elementer satt inn før de opprinnelige elementene.

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

Oppdatering 2018-08-17: Ytelse

Jeg hadde til hensikt at dette svaret skulle presentere en alternativ syntaks som jeg mener er mer minneverdig og konsis. Det bør bemerkes at ifølge noen referanserammer (se dette andre svaret), er denne syntaksen betydelig tregere. Dette vil sannsynligvis ikke ha betydning med mindre du utfører mange av disse operasjonene i en løkke.

Svar #3

Hvis du legger til et array foran et annet array, er det mer effektivt å bare bruke concat. Så:

const newArray = [1, 2, 3].concat([4, 5]);
newArray; // [1, 2, 3, 4, 5]

Men dette vil fortsatt være O(N) i størrelsen på oldArray. Likevel er det mer effektivt enn å manuelt iterere over oldArray. Avhengig av detaljene kan det også hjelpe deg, for hvis du skal legge til mange verdier først, er det bedre å legge dem i et array først og deretter concatenere oldArray på slutten, i stedet for å legge til hver enkelt for seg.

Det finnes ingen måte å gjøre det bedre enn O(N) i størrelsen på oldArray, fordi arrayer lagres i sammenhengende minne med det første elementet i en fast posisjon. Hvis du vil sette inn før det første elementet, må du flytte alle de andre elementene. Hvis du trenger en måte å omgå dette på, gjør det @GWW sa og bruk en lenket liste, eller en annen datastruktur.

Svar #4

Hvis du vil legge til et array (a1) foran et array a2, kan du bruke følgende:

var a1 = [1, 2];
var a2 = [3, 4];
Array.prototype.unshift.apply(a1, a2);
console.log(a1);
// => [3, 4, 1, 2]

Svar #5

På en uforanderlig måte er dette sannsynligvis den beste måten:

const x = 1
const list = [2, 3, 4]
const newList = [x].concat(list) // [1, 2, 3, 4]

Relaterte artikler