La forma más eficiente de anteponer un valor a una matriz

268

Suponiendo que tengo una matriz que tiene un tamaño de N(donde N > 0), ¿hay una forma más eficiente de anteponer a la matriz que no requeriría O (N + 1) pasos?

En el 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;
}
samccone
fuente
tanto como amo y listas de punteros Siento como si vinculados debe haber una manera más eficaz de hacer las cosas que utilizan tipos de datos nativos JS
samccone
@samccone: Sí, ignore mi comentario, lo siento, pensé que había dicho Java: P
GWW
3
Java, JavaScript, C o Python, no importa qué idioma: la compensación de la complejidad entre las matrices frente a las listas vinculadas es la misma. Las listas enlazadas probablemente sean bastante difíciles de manejar en JS porque no hay una clase incorporada para ellas (a diferencia de Java), pero si lo que realmente quiere es el tiempo de inserción O (1), entonces quiere una lista enlazada.
mgiuca 01 de
1
¿Es un requisito clonarlo?
Ryan Florence
1
Si es un requisito clonarlo, entonces el desplazamiento no es apropiado, ya que mutará la matriz original y no creará una copia.
mgiuca 01 de

Respuestas:

493

No estoy seguro de que sea más eficiente en términos de big-O, pero ciertamente usar el unshiftmétodo 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 unshiftes decentemente más rápido en al menos un par de navegadores, independientemente de un posible rendimiento de big-O diferente si está de acuerdo con modificar la matriz en el lugar. Si realmente no puede mutar la matriz original, entonces haría algo como el fragmento a continuación, que no parece ser apreciablemente más rápido que su solución:

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

[Editar 2]

Para completar, la siguiente función se puede utilizar en lugar del ejemplo de OP prependArray(...)para aprovechar el unshift(...)método 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];
maerics
fuente
190
¿Quién decidió llamar prepend" unshift"?
Scott Stafford
12
@ScottStafford unshiftsuena más apropiado para una operación de matriz de este tipo (mueve los elementos ... más o menos físicamente). prependsería más apropiado para las listas vinculadas, donde literalmente antepone elementos.
CamilB
12
Unshift es la función complementaria de shift. Llamarlo "anteponer" sería una elección extraña. Unshift es cambiar como push es hacer pop.
Sir Robert el
9
Solo un problema con esta solución. ¿Unshift () no devuelve su longitud , y no la matriz como en esta respuesta? w3schools.com/jsref/jsref_unshift.asp
iDVB
44
pushy unshiftambos contienen u, mientras que popy shiftno tienen.
Qian Chen
70

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

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. Esto probablemente no va a importar a menos que esté haciendo muchas de estas operaciones en un bucle.

Frank Tan
fuente
44
Esto debería ser votado a partir de 2017. Es conciso. Al usar spread, devuelve la nueva secuencia, que puede ser útil para encadenar modificaciones adicionales. También es puro (lo que significa que ayb no se ven afectados)
Simon
No mencionaste el tiempo necesario en comparación conunshift
Shashank Vivek
Gracias @ShashankVivek. Tenía la intención de que esta respuesta presentara una sintaxis alternativa que creo que es más memorable y concisa. Voy a actualizar.
Frank Tan
@FrankTan: Cheers :) +1
Shashank Vivek
46

Si está anteponiendo una matriz al frente de otra matriz, es más eficiente usarla concat. Entonces:

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 forma de hacerlo mejor que O (N) en el tamaño de oldArray, porque las matrices se almacenan en la memoria contigua con el primer elemento en una posición fija. Si desea insertar antes del primer elemento, debe mover todos los demás elementos. Si necesita una solución, haga lo que dijo @GWW y use una lista vinculada o una estructura de datos diferente.

mgiuca
fuente
2
Oh sí, me olvidé unshift. Pero tenga en cuenta que a) que muta oldArray mientras concatque no lo hace (por lo que cuál es mejor para usted depende de la situación), yb) solo inserta un elemento.
mgiuca 01 de
1
Wow, eso es mucho más lento. Bueno, como dije, está haciendo una copia de la matriz (y también está creando una nueva matriz [0]), mientras que unshift la está mutando en el lugar. Pero ambos deberían ser O (N). También aplaude el enlace a ese sitio, parece muy útil.
mgiuca 01 de
2
es bueno para oneliner, ya que concat devuelve la matriz y unshift devuelve la nueva duración
Z. Khullah
32

Si desea anteponer una matriz (a1 con una matriz 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]
uroslatos
fuente
6

Si necesita preservar la matriz anterior, divida la antigua y desplace los nuevos valores al comienzo 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
*/
Kennebec
fuente
4

Tengo algunas pruebas nuevas de diferentes métodos de prepending. Para matrices pequeñas (<1000 elems), el líder es para ciclo acoplado con un método push. Para grandes matrices, 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 más de 100 veces más lenta en todos los navegadores.

https://jsbench.me/cgjfc79bgx/1

John Klimov
fuente
¡Gran respuesta! Pero para asegurarse de no perder parte de él, puede reproducir sus casos de prueba aquí (tal vez con algunos resultados de ejecución de muestra) en caso de que, por ejemplo, jsbench desaparezca.
ruffin
3

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]
bjornd
fuente
2
No ... unshift agregará una matriz como primer argumento: var a = [4, 5]; a.unshift ([1,2,3]); console.log (a); // -> [[4, 5], 1, 2, 3]
enero
44
¡Estás en lo correcto! Tendrías que usarloArray.prototype.unshift.apply(a,b);
david
1

Ejemplo de anteponer en el lugar:

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

A.unshift(...B)

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

Miguel Mota
fuente
1

Llamar unshiftsolo devuelve la longitud de la nueva matriz. Entonces, para agregar un elemento al principio y devolver una nueva matriz, hice esto:

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

o simplemente con operador de propagación:

[ newVal, ...array ]

De esta manera, la matriz original permanece intacta.

rehman_00001
fuente