tutorial - Javascript: ¿Cuál es el rendimiento algorítmico de ''empalme''?

javascript tutorial

Question

Es decir, ¿sería más adecuado utilizar algún tipo de estructura de datos de árbol o lista de omisión si necesito llamar mucho esta función para inserciones de matrices individuales?

Answer 1

Esta es una buena regla general, basada en las pruebas realizadas en Chrome, Safari y Firefox: empalmar un solo valor en el medio de una matriz es aproximadamente la mitad de rápido que empujar / cambiar un valor a un extremo de la matriz. (Nota: Solo probado en una matriz de tamaño 10,000).

http://jsperf.com/splicing-a-single-value

Eso es bastante rápido. Por lo tanto, es poco probable que tenga que ir tan lejos como para implementar otra estructura de datos con el fin de exprimir más el rendimiento.

Actualización : Como lo señala eBusiness en los comentarios a continuación, la prueba realiza una operación de copia costosa junto con cada splice , push y shift , lo que significa que subestima la diferencia en el rendimiento. Aquí hay una prueba revisada que evita la copia de la matriz, por lo que debería ser mucho más precisa: http://jsperf.com/splicing-a-single-value/19

Answer 2

Mover un solo valor

// tmp = arr[1][i];
// arr[1].splice(i, 1); // splice is slow in FF
// arr[1].splice(end0_1, 0, tmp);

 tmp = arr[1][i];
 ii = i;
 while (ii<end0_1)
  {
  arr[1][ii] = arr[1][++ii];
cycles++;
  }
 arr[1][end0_1] = tmp;

Answer 3

Puede considerar si desea utilizar un objeto en su lugar; todos los objetos de JavaScript (incluidas las instancias de Array ) son conjuntos (altamente optimizados) de pares clave / valor con un prototipo opcional. Una implementación debe (tenga en cuenta que no tengo "un algoritmo de hashing de rendimiento razonable"). ( Actualización : Eso fue en 2010. Aquí, en 2018, los objetos están altamente optimizados en todos los motores de JavaScript importantes).

Aparte de eso, el rendimiento del splice va a variar mucho entre las implementaciones (por ejemplo, los proveedores). Esta es una razón por la que "no optimizar prematuramente" es un consejo aún más apropiado para las aplicaciones de JavaScript que se ejecutarán en implementaciones de múltiples proveedores (aplicaciones web, por ejemplo) que incluso para la programación normal. Mantenga su código bien modularizado y resuelva los problemas de rendimiento cuando se produzcan.