javascript - La forma más eficiente de anteponer un valor a un arreglo

Suponiendo que tengo un arreglo que tiene un tamaño de N (donde N > 0), ¿hay una forma más eficiente de anteponer elementos al arreglo que no requiera O(N + 1) pasos?

En código, esencialmente, lo que actualmente estoy haciendo es

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

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

  return newArray;
}

Respuesta #1

No estoy seguro acerca de ser más eficiente en términos de big-O, pero ciertamente usar el método unshift es más conciso:

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

[Editar]

Este benchmark de jsPerf muestra que unshift es bastante más rápido en al menos un par de navegadores, independientemente de un posible rendimiento diferente en notación big-O si estás de acuerdo con modificar el arreglo en el lugar. Si realmente no puedes modificar el arreglo original, entonces harías algo como el siguiente fragmento, que no parece ser notablemente más rápido que tu solución:

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

[Editar 2]

Para mayor completitud, la siguiente función puede usarse en lugar del ejemplo de OP prependArray(...) para aprovechar el método unshift(...) de Array:

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

Respuesta #2

Con ES6, ahora puedes usar el operador spread para crear un nuevo arreglo con tus nuevos elementos insertados antes de los elementos originales.

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

Actualización 2018-08-17: Rendimiento

Tenía la intención de que esta respuesta presentara una sintaxis alternativa que creo que es más memorable y concisa. Cabe señalar que, según algunos puntos de referencia (ver esta otra respuesta), esta sintaxis es significativamente más lenta. Probablemente esto no importará a menos que estés realizando muchas de estas operaciones en un bucle.

Respuesta #3

Si estás anteponiendo un arreglo al principio de otro arreglo, es más eficiente simplemente usar concat. Entonces:

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

Pero esto todavía será O(N) en el tamaño de oldArray. Aun así, es más eficiente que iterar manualmente sobre oldArray. Además, dependiendo de los detalles, puede ayudarte, porque si vas a anteponer muchos valores, es mejor ponerlos en un array primero y luego concatenar oldArray al final, en lugar de anteponer cada uno individualmente.

No hay forma de hacerlo mejor que O(N) en el tamaño de oldArray, porque los arreglos se almacenan en memoria contigua con el primer elemento en una posición fija. Si quieres insertar antes del primer elemento, necesitas mover todos los demás elementos. Si necesitas una forma de evitar esto, haz lo que dijo @GWW y usa una lista enlazada, o una estructura de datos diferente.

Respuesta #4

Si desea anteponer el arreglo (a1 con un arreglo a2) puede usar lo siguiente:

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

Respuesta #5

De manera inmutable, esta es probablemente la mejor manera:

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