Die effizienteste Methode, um einem Array einen Wert voranzustellen

267

Angenommen, ich habe ein Array mit einer Größe von N(wo N > 0), gibt es eine effizientere Möglichkeit, dem Array ein Präfix hinzuzufügen, für das keine O (N + 1) -Schritte erforderlich wären?

Im Code mache ich im Wesentlichen Folgendes

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

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

  return newArray;
}
Samccone
quelle
So sehr ich verknüpfte Listen und Zeiger liebe, habe ich das Gefühl, dass es eine effektivere Möglichkeit geben muss, Dinge mit nativen JS-Datentypen zu tun
Samccone
@samccone: Ja, ignoriere meinen Kommentar, sorry, ich dachte du sagtest Java: P
GWW
3
Java, JavaScript, C oder Python, egal in welcher Sprache: Der Kompromiss zwischen Arrays und verknüpften Listen ist der gleiche. Verknüpfte Listen sind in JS wahrscheinlich ziemlich unhandlich, da für sie keine integrierte Klasse vorhanden ist (im Gegensatz zu Java). Wenn Sie jedoch wirklich eine Einfügezeit von O (1) wünschen, möchten Sie eine verknüpfte Liste.
mgiuca
1
Ist es eine Anforderung, es zu klonen?
Ryan Florence
1
Wenn es erforderlich ist, es zu klonen, ist das Aufheben der Verschiebung unangemessen, da es das ursprüngliche Array mutiert und keine Kopie erstellt.
mgiuca

Antworten:

491

Ich bin mir nicht sicher, ob Big-O effizienter ist, aber die Verwendung der unshiftMethode ist sicherlich prägnanter:

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

[Bearbeiten]

Dieser jsPerf-Benchmark zeigt, dass er unshiftin mindestens einigen Browsern anständig schneller ist, unabhängig von der möglicherweise unterschiedlichen Big-O-Leistung, wenn Sie das Array direkt ändern können . Wenn Sie das ursprüngliche Array wirklich nicht mutieren können, würden Sie so etwas wie das folgende Snippet ausführen, das nicht wesentlich schneller zu sein scheint als Ihre Lösung:

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

[Bearbeiten 2]

Der Vollständigkeit halber kann anstelle des OP-Beispiels die folgende Funktion verwendet werden prependArray(...), um die Array- unshift(...)Methode zu nutzen:

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];
Maerics
quelle
190
Wer hat beschlossen, prepend" unshift" anzurufen ?
Scott Stafford
12
@ScottStafford unshiftklingt für eine solche Array-Operation besser geeignet (es verschiebt die Elemente ... mehr oder weniger physisch). prependwäre besser für verknüpfte Listen geeignet, bei denen Sie Elemente buchstäblich voranstellen.
CamilB
12
Verschieben ist die komplementäre Funktion zum Verschieben. Es "vorangestellt" zu nennen, wäre die seltsame Wahl. Unshift ist zu verschieben, während Push zu Pop ist.
Sir Robert
9
Nur ein Problem mit dieser Lösung. Gibt unshift () nicht seine Länge zurück und nicht das Array wie in dieser Antwort? w3schools.com/jsref/jsref_unshift.asp
iDVB
4
pushund unshiftbeide enthalten u, während popund shiftnicht haben.
Qian Chen
70

Mit ES6 können Sie jetzt den Spread-Operator verwenden , um ein neues Array mit Ihren neuen Elementen zu erstellen, die vor den ursprünglichen Elementen eingefügt werden.

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

Update 2018-08-17: Leistung

Ich wollte mit dieser Antwort eine alternative Syntax präsentieren, die meiner Meinung nach einprägsamer und prägnanter ist. Es ist zu beachten, dass diese Syntax gemäß einigen Benchmarks (siehe diese andere Antwort ) erheblich langsamer ist. Dies wird wahrscheinlich keine Rolle spielen, es sei denn, Sie führen viele dieser Operationen in einer Schleife aus.

Frank Tan
quelle
4
Dies sollte ab 2017 abgestimmt werden. Es ist prägnant. Durch die Verwendung von Spread wird der neue Stream zurückgegeben, der nützlich sein kann, um weitere Änderungen zu verketten. Es ist auch rein (was bedeutet, dass a und b nicht betroffen sind)
Simon
Sie didnt abt die Zeit genommen erwähnen im Vergleich zuunshift
Shashank Vivek
Danke @ShashankVivek. Ich wollte mit dieser Antwort eine alternative Syntax präsentieren, die meiner Meinung nach einprägsamer und prägnanter ist. Ich werde aktualisieren.
Frank Tan
@FrankTan: Prost :) +1
Shashank Vivek
46

Wenn Sie ein Array vor ein anderes Array stellen, ist es effizienter, es nur zu verwenden concat. So:

var newArray = values.concat(oldArray);

Dies ist jedoch immer noch O (N) in der Größe von oldArray. Trotzdem ist es effizienter als das manuelle Iterieren über oldArray. Abhängig von den Details kann es Ihnen auch helfen, denn wenn Sie viele Werte voranstellen möchten, ist es besser, sie zuerst in ein Array einzufügen und dann am Ende mit oldArray zu verknüpfen, als jeden einzeln vorzustellen.

Es gibt keine bessere Möglichkeit als O (N) in der Größe von oldArray, da Arrays im zusammenhängenden Speicher mit dem ersten Element an einer festen Position gespeichert werden. Wenn Sie vor dem ersten Element einfügen möchten, müssen Sie alle anderen Elemente verschieben. Wenn Sie dies umgehen möchten, tun Sie, was @GWW gesagt hat, und verwenden Sie eine verknüpfte Liste oder eine andere Datenstruktur.

mgiuca
quelle
2
Oh ja, ich habe es vergessen unshift. Beachten Sie jedoch, dass a) das oldArray mutiert, während concatdies nicht der Fall ist (welches für Sie besser ist, hängt von der Situation ab), und b) nur ein Element einfügt.
mgiuca
1
Wow, das ist viel langsamer. Nun, wie gesagt, es wird eine Kopie des Arrays erstellt (und auch ein neues Array erstellt [0]), während durch Verschieben das Array an Ort und Stelle mutiert wird. Aber beide sollten O (N) sein. Auch Prost auf den Link zu dieser Seite - sieht sehr praktisch aus.
mgiuca
2
Es ist gut für Oneliner, da Concat das Array zurückgibt und Unshift die neue Länge zurückgibt
Z. Khullah
32

Wenn Sie dem Array (a1 ein Array a2) voranstellen möchten, können Sie Folgendes verwenden:

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

Wenn Sie das alte Array beibehalten müssen, schneiden Sie das alte auf und verschieben Sie die neuen Werte an den Anfang des Slice.

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
quelle
4

Ich habe einige neue Tests verschiedener Methoden zum Voranstellen. Bei kleinen Arrays (<1000 Elemente) ist der Leader für den Zyklus mit einer Push-Methode gekoppelt. Bei großen Arrays wird die Unshift-Methode zum Marktführer.

Diese Situation gilt jedoch nur für den Chrome-Browser. In Firefox hat unshift eine großartige Optimierung und ist in allen Fällen schneller.

Die ES6-Verbreitung ist in allen Browsern mehr als 100-mal langsamer.

https://jsbench.me/cgjfc79bgx/1

John Klimov
quelle
Gute Antwort! Um sicherzustellen, dass Sie keinen Teil davon verlieren, können Sie Ihre Testfälle hier reproduzieren (möglicherweise mit einigen Beispiellaufergebnissen), falls z. B. jsbench nicht mehr verwendet wird.
Ruffin
3

Es gibt eine spezielle Methode:

a.unshift(value);

Wenn Sie dem Array jedoch mehrere Elemente voranstellen möchten, ist die Verwendung einer solchen Methode schneller:

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
quelle
2
Nein ... durch Verschieben wird als erstes Argument ein Array hinzugefügt: var a = [4, 5]; a.unshift ([1,2,3]); console.log (a); // -> [[4, 5], 1, 2, 3]
bjornd
4
Du hast Recht! Sie müssten verwendenArray.prototype.unshift.apply(a,b);
David
1

Beispiel für das Voranstellen vor Ort:

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

A.unshift(...B)

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

Miguel Mota
quelle
1

Beim Aufrufen wird unshiftnur die Länge des neuen Arrays zurückgegeben. Um am Anfang ein Element hinzuzufügen und ein neues Array zurückzugeben, habe ich Folgendes getan:

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

oder einfach mit Spread Operator:

[ newVal, ...array ]

Auf diese Weise bleibt das ursprüngliche Array unberührt.

rehman_00001
quelle