javascript - first - La forma más eficiente de anteponer un valor a una matriz
unshift javascript (7)
Suponiendo que tengo una matriz que tiene un tamaño de N (donde N > 0 ), ¿hay una forma más eficiente de prepagar a la matriz que no requeriría pasos O (N + 1)?
En código, esencialmente, lo que estoy haciendo actualmente es
function prependArray(value, oldArray) {
var newArray = new Array(value);
for(var i = 0; i < oldArray.length; ++i) {
newArray.push(oldArray[i]);
}
return newArray;
}
Con ES6, ahora puede usar el operador de propagación para crear una nueva matriz con sus nuevos elementos insertados antes que 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
Intenté que esta respuesta presentara una sintaxis alternativa que creo que es más memorable y concisa. Cabe señalar que de acuerdo con algunos puntos de referencia (ver esta otra respuesta ), esta sintaxis es significativamente más lenta. Es probable que esto no sea importante a menos que esté realizando muchas de estas operaciones en un bucle.
Hay un método especial:
a.unshift(value);
Pero si desea anteponer varios elementos a la matriz, sería más rápido utilizar dicho método:
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]
No estoy seguro de que sea más eficiente en términos de big-O, pero ciertamente usar el método de cambio es más conciso:
var a = [1, 2, 3, 4];
a.unshift(0);
a; // => [0, 1, 2, 3, 4]
[Editar]
Este punto de referencia jsPerf muestra que unshift es decentemente más rápido en al menos un par de navegadores, independientemente de la unshift un gran O grande diferente si está de acuerdo con la modificación de la matriz en el lugar. Si realmente no puede mutar la matriz original, entonces haría algo como el siguiente fragmento de código, que no parece ser mucho más rápido que su solución:
a.slice().unshift(0); // Use "slice" to avoid mutating "a".
[Editar 2]
Para completar, se puede usar la siguiente función en lugar del ejemplo prependArray(...) de OP para aprovechar el método unshift(...) 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];
Si desea anteponer array (a1 con un array 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]
Si está anteponiendo una matriz al frente de otra matriz, es más eficiente usar solo concat . Asi que:
var newArray = values.concat(oldArray);
Pero esto seguirá siendo O (N) en el tamaño de oldArray. Aún así, es más eficiente que iterar manualmente sobre oldArray. Además, dependiendo de los detalles, puede ayudarlo, porque si va a anteponer muchos valores, es mejor colocarlos primero en una matriz y luego concat oldArray al final, en lugar de anteponer cada uno individualmente.
No hay manera de hacerlo mejor que O (N) en el tamaño de oldArray, porque los arreglos se almacenan en una memoria contigua con el primer elemento en una posición fija. Si desea insertar antes del primer elemento, necesita mover todos los demás elementos. Si necesita una forma de evitar esto, haga lo que @GWW dijo y use una lista vinculada o una estructura de datos diferente.
Si necesita conservar la matriz anterior, corte la anterior y desplace los nuevos valores al principio de la división.
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
*/
Tengo algunas nuevas pruebas de diferentes métodos de preparación. Para matrices pequeñas (<1000 elementos), el líder es para ciclos acoplados con un método de empuje. Para matrices enormes, el método Unshift se convierte en el líder.
Pero esta situación es real solo para el navegador Chrome. En Firefox, unshift tiene una optimización impresionante y es más rápido en todos los casos.
La propagación de ES6 es 100 veces más lenta en todos los navegadores.