Effizienteste Methode, einen Wert einem Array voranzustellen

Question

Angenommen, ich habe ein Array mit einer Größe von N (wobei N > 0 ), gibt es einen effizienteren Weg, dem Array etwas voranzustellen, der nicht O(N + 1) Schritte erfordern würde?

Im Code bedeutet das, was ich derzeit tue, im Wesentlichen

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

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

  return newArray;
}

Answer 1

Ich bin mir nicht sicher, ob es in Bezug auf Big-O effizienter ist, aber sicherlich ist die Verwendung des unshift Methode ist prägnanter:

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

[Editar]

Diese jsPerf-Benchmark zeigt, dass unshift ist zumindest in einigen Browsern deutlich schneller, ungeachtet der möglicherweise unterschiedlichen Big-O-Leistung si Sie sind mit der Änderung des Arrays an Ort und Stelle einverstanden. Wenn Sie wirklich nicht das ursprüngliche Array mutieren können, dann würden Sie etwas wie das unten stehende Snippet tun, die nicht scheinen, spürbar schneller als Ihre Lösung zu sein:

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

[Bearbeiten 2]

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

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

Answer 2

Mit ES6 können Sie jetzt die Spread-Operator um ein neues Array zu erstellen, in das die neuen Elemente 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

Mit dieser Antwort wollte ich eine alternative Syntax vorstellen, die meiner Meinung nach einprägsamer und prägnanter ist. Es sollte beachtet werden, dass nach einigen Benchmarks (siehe diese andere Antwort ), ist diese Syntax deutlich langsamer. Dies ist wahrscheinlich nicht von Bedeutung, es sei denn, Sie führen viele dieser Operationen in einer Schleife aus.

Answer 3

Wenn Sie ein Array einem anderen Array voranstellen, ist es effizienter, einfach die Funktion concat . Also:

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

Aber dies wird immer noch O(N) in der Größe von oldArray sein. Dennoch ist es effizienter als eine manuelle Iteration über oldArray. Abhängig von den Details kann es Ihnen auch helfen, denn wenn Sie viele Werte voranstellen wollen, ist es besser, sie zuerst in ein Array zu packen und dann oldArray am Ende zu konkatieren, als jeden Wert einzeln voranzustellen.

Es gibt keine Möglichkeit, die Größe von oldArray besser als O(N) zu bestimmen, da Arrays in zusammenhängendem Speicher gespeichert werden, wobei das erste Element an einer festen Position liegt. Wenn Sie vor dem ersten Element einfügen wollen, müssen Sie alle anderen Elemente verschieben. Wenn Sie dies umgehen wollen, tun Sie, was @GWW sagte, und verwenden Sie eine verknüpfte Liste oder eine andere Datenstruktur.

Answer 4

Wenn Sie einem 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]

Answer 5

In einer unveränderlichen Weise ist dies wahrscheinlich der beste Weg:

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