into - splice javascript

¿Por qué array.push a veces es más rápido que array[n]=value?

Question

Como resultado secundario de probar algún código, escribí una pequeña función para comparar la velocidad de uso del método array.push versus direccionamiento directo (array [n] = value). Para mi sorpresa, el método push a menudo parecía ser más rápido, especialmente en Firefox y, a veces, en Chrome. Solo por curiosidad: ¿alguien tiene una explicación para eso? Puede encontrar la prueba en esta página (haga clic en ''Comparación de métodos de matriz'')

Answer 1

Aquí hay un buen testbed, que confirma que la asignación directa es significativamente más rápida que push: http://jsperf.com/array-direct-assignment-vs-push .

Editar: parece haber algún problema al mostrar datos de resultados acumulativos, pero con suerte se soluciona pronto.

Answer 2

Estos son los resultados que obtengo con su prueba

en Safari:

• Array.push (n) 1,000,000 de valores: 0,142 seg
• Matriz [n .. 0] = valor (descendente) 1,000,000 de valores: 3,697 seg
• Matriz [0 .. n] = valor (ascendente) 1,000,000 de valores: 0.073 seg

en Firefox:

• Array.push (n) 1,000,000 de valores: 0.075 seg
• Matriz [n .. 0] = valor (descendente) 1,000,000 de valores: 1.193 sec
• Matriz [0 .. n] = valor (ascendente) 1,000,000 de valores: 0.055 sec

en IE7:

• Array.push (n) 1,000,000 de valores: 2,828 segundos
• Matriz [n .. 0] = valor (descendente) 1,000,000 de valores: 1.141 seg
• Matriz [0 .. n] = valor (ascendente) 1,000,000 de valores: 7.984 sec

De acuerdo con su prueba, el método push parece ser mejor en IE7 (gran diferencia), y como en los otros navegadores la diferencia es pequeña, parece ser el método push realmente la mejor manera de agregar elementos a una matriz.

Pero creé otro script de prueba simple para verificar qué método es más rápido para agregar valores a una matriz, los resultados realmente me sorprendieron, el uso de Array.length parece ser mucho más rápido en comparación con el uso de Array.push , así que realmente no sé qué para decir o pensar más, no tengo idea.

Por cierto: en mi IE7 tu script se detiene y los navegadores me preguntan si quiero que continúe (ya conoces el típico mensaje de IE que dice: "¿Dejar de ejecutar este script? ...") Recomiendo reducir un poco los bucles .

Answer 3

Push lo agrega al final, mientras que el array [n] tiene que pasar por la matriz para encontrar el lugar correcto. Probablemente dependa del navegador y de su forma de manejar matrices.

Answer 4

Todo tipo de factores entran en juego, la mayoría de las implementaciones de JS usan una matriz plana que se convierte en almacenamiento disperso si es necesario más adelante.

Básicamente, la decisión de convertirse en dispersa es una heurística basada en qué elementos se están estableciendo y cuánto espacio se desperdiciará para mantenerse plano.

En su caso, está configurando el último elemento primero, lo que significa que el motor JS verá una matriz que necesita tener una longitud de n pero solo un elemento. Si n es lo suficientemente grande, esto hará que la matriz sea dispersa: en la mayoría de los motores, esto significa que todas las inserciones posteriores tomarán el caso de matriz escasa y lenta.

Debe agregar una prueba adicional en la que complete la matriz desde el índice 0 hasta el índice n-1: debería ser mucho, mucho más rápido.

En respuesta a @Christoph y por el deseo de posponer las cosas, aquí hay una descripción de cómo las matrices (generalmente) se implementan en JS: las especificaciones varían desde el motor JS hasta el motor JS, pero el principio general es el mismo.

Todos los Object JS (por lo tanto, cadenas, números, verdadero, falso, undefined o null ) heredan de un tipo de objeto base: la implementación exacta varía, puede ser herencia C ++ o manualmente en C (hay beneficios al hacerlo de cualquier manera): el tipo de objeto base define los métodos de acceso a la propiedad predeterminados, por ej.

interface Object {
    put(propertyName, value)
    get(propertyName)
private:
    map properties; // a map (tree, hash table, whatever) from propertyName to value
}

Este tipo de objeto maneja toda la lógica de acceso a propiedades estándar, la cadena de prototipos, etc. Luego, la implementación de la matriz se convierte en

interface Array : Object {
    override put(propertyName, value)
    override get(propertyName)
private:
    map sparseStorage; // a map between integer indices and values
    value[] flatStorage; // basically a native array of values with a 1:1
                         // correspondance between JS index and storage index
    value length; // The `length` of the js array
}

Ahora cuando crea una matriz en JS, el motor crea algo similar a la estructura de datos anterior. Cuando inserta un objeto en la instancia de Array, el método put de la Array comprueba si el nombre de la propiedad es un entero (o puede convertirse en un entero, por ejemplo, "121", "2341", etc.) entre 0 y 2 ^ 32 -1 (o posiblemente 2 ^ 31-1, me olvido exactamente). Si no lo es, entonces el método put se reenvía a la implementación del objeto base y se completa la lógica estándar [[Put]]. De lo contrario, el valor se coloca en el propio almacenamiento de la matriz, si los datos son suficientemente compactos, el motor utilizará el almacenamiento en matriz plana, en cuyo caso la inserción (y recuperación) es solo una operación de indexación estándar, de lo contrario el motor convertirá la matriz al almacenamiento disperso, y poner / usar un mapa para obtener desde propertyName a ubicación de valor.

Honestamente, no estoy seguro de si algún motor JS actualmente se convierte de almacenamiento disperso a plano después de que se produce la conversión.

De todos modos, esa es una descripción general de alto nivel de lo que sucede y deja de lado algunos de los detalles más complicados, pero ese es el patrón general de implementación. Los detalles de cómo se distribuye el almacenamiento adicional, y cómo se entrega / se obtiene difiere de un motor a otro, pero esto es lo más claro que puedo describir realmente el diseño / implementación.

Un punto de suma menor, mientras que la especificación ES se refiere a propertyName como una cadena. Los motores JS tienden a especializarse también en búsquedas enteras, por lo que someObject[someInteger] no convertirá el entero en una cadena si estás mirando un objeto que tiene un entero propiedades por ej. Array, String y DOM tipos ( NodeList s, etc.).

Answer 5

push() es un caso especial del [[Put] más general y, por lo tanto, se puede optimizar aún más:

Cuando se llama a [[Put]] en un objeto de matriz, primero se debe convertir el argumento en un entero sin signo porque todos los nombres de propiedad, incluidos los índices de matriz, son cadenas. Luego se tiene que comparar con la propiedad de longitud de la matriz para determinar si se debe aumentar la longitud o no. Al presionar, no debe tener lugar ninguna conversión o comparación: simplemente use la longitud actual como índice de matriz y auméntela.

Por supuesto, hay otras cosas que afectarán el tiempo de ejecución, por ejemplo, llamar a push() debería ser más lento que llamar a [[Put]] a través de [] porque la cadena del prototipo debe verificarse para el primero.

Como señaló Olliej: las implementaciones actuales de ECMAScript optimizarán la conversión, es decir, para los nombres de propiedades numéricas, no se realiza ninguna conversión de cadena a uint, sino simplemente una verificación de tipo simple. La suposición básica aún debe mantenerse, aunque su impacto será menor de lo que originalmente asumí.