Es decir, ¿estaría mejor preparado para usar algún tipo de árbol o estructura de datos de lista de omisiones si necesito llamar mucho a esta función para inserciones de matriz individuales?Javascript: ¿Cuál es el rendimiento algorítmico de 'empalme'?
En su lugar, puede considerar si desea utilizar un mapa recto; todos los objetos JavaScript (incluidas las instancias Array) son mapas, por lo que una implementación debería (tenga en cuenta que no digo "no") tiene un algoritmo hash de rendimiento razonable.
Aparte de eso, el rendimiento de splice va a variar un lote entre las implementaciones (por ejemplo, los proveedores). Esta es una razón por la cual "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) de lo que es incluso para la programación normal. Mantenga su código bien modularizado y aborde los problemas de rendimiento cuando ocurran.
Problema con un mapa es que no creo que pueda repetirlo en orden ordenado ... – Hamster
@Hamster: Puede hacerlo, pero solo buscando todas las claves, clasificándolas y luego recorriendo esa lista. Si tienes que hacerlo mucho, entonces probablemente estés mejor con un 'Array' (que en JavaScript es, después de todo, solo un mapa con una orden definida y una propiedad mágica de 'longitud'). –
@ T.J.Crowder ¿Qué sucede si tengo que insertar un elemento en un índice específico entre los elementos ya existentes (es decir, mantenerlos y reordenar los índices) con frecuencia, y hay miles de elementos? Sé que puedo hacerlo con 'empalme', pero ¿es una' Matriz' con 'empalme' una estructura de datos adecuada para tal tarea? Si no, ¿qué otra estructura de datos JS podría ser adecuada para esto? – tonix
Aquí hay una buena regla general, basada en las pruebas realizadas en Chrome, Safari y Firefox: empalmar un único valor en el medio de una matriz es aproximadamente la mitad de rápido como empujando/cambiando un valor a un extremo del formación. (Nota: Sólo 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 rendimiento.
actualización: Como el comercio electrónico señala en los comentarios a continuación, la prueba realiza una operación de copia caros junto con cada splice, push y shift, lo que significa que subestima la diferencia en el rendimiento. Aquí está una prueba revisada que evita la copia matriz, por lo que debe ser mucho más preciso: http://jsperf.com/splicing-a-single-value/19
En realidad, depende completamente de la longitud de la matriz. Si cambia a una matriz de 100.000 elementos, entonces empalmar un valor en el medio es un 95% más lento que agregar un valor al final, según lo medido por su prueba jsperf. Eso es porque insertar en el medio es O (n) en el tamaño de la matriz, mientras que insertar en el extremo puede ser O (1). – Geoff
-1 Esa prueba jsperf está contaminada por la copia de una matriz, en su mayoría se mide el tiempo que lleva crear una nueva matriz de 10000 elementos. – aaaaaaaaaaaa
@eBusiness Por favor, amplíe su reclamo. ¿Dónde en las pruebas se copia la matriz? –
movimiento único valor
// \t tmp = arr[1][i];
// \t arr[1].splice(i, 1); \t // splice is slow in FF
// \t arr[1].splice(end0_1, 0, tmp);
\t tmp = arr[1][i];
\t ii = i;
\t while (ii<end0_1)
\t \t {
\t \t arr[1][ii] = arr[1][++ii];
cycles++;
\t \t }
\t arr[1][end0_1] = tmp;
Prueba de ello! Esa es la mejor manera de responder a esta pregunta ... – Harmen
¿Cuál es una buena manera de probar esto? – Hamster
Si las matrices de JavaScript son realmente matrices, es O (n). – Gumbo