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

Entran en juego todo tipo de factores, la mayoría de las implementaciones de JS utilizan una matriz plana que se convierte en almacenamiento escaso si es necesario más adelante.

Básicamente, la decisión de volverse disperso es una heurística basada en qué elementos se están configurando y cuánto espacio se desperdiciaría para permanecer plano.

En su caso, está configurando primero el último elemento, lo que significa que el motor JS verá una matriz que debe tener una longitud de nun solo elemento. Si nes lo suficientemente grande, esto inmediatamente convertirá la matriz en una matriz dispersa; en la mayoría de los motores, esto significa que todas las inserciones posteriores tomarán el caso de matriz dispersa lenta.

Debería agregar una prueba adicional en la que llene 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 deseo de posponer las cosas, aquí hay una descripción de cómo se implementan (generalmente) las matrices en JS: los detalles varían de un motor JS a otro, pero el principio general es el mismo.

Todos Objectlos JS (por lo tanto, no cadenas, números, verdadero, falso undefinedo null) heredan de un tipo de objeto base; la implementación exacta varía, podría ser herencia de 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 ejemplo.

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 Array 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 parecido a la estructura de datos anterior. Cuando inserta un objeto en la instancia de Array, el método put de Array verifica si el nombre de la propiedad es un número entero (o se puede convertir en un número entero, por ejemplo, "121", "2341", etc.) entre 0 y 2^32. -1 (o posiblemente 2^31-1, lo olvido exactamente). Si no es así, entonces el método put se reenvía a la implementación del objeto base y se realiza la lógica [[Put]] estándar. De lo contrario, el valor se coloca en el propio almacenamiento de la matriz; si los datos son lo suficientemente compactos, entonces el motor utilizará el almacenamiento de matriz plana, en cuyo caso la inserción (y recuperación) es solo una operación de indexación de matriz estándar; de lo contrario, el motor convertirá la matriz. para almacenamiento escaso y poner/obtener uso de un mapa para ir desde el nombre de propiedad hasta la ubicación del valor.

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

De todos modos, esa es una descripción general de nivel bastante alto de lo que sucede y omite algunos de los detalles más repugnantes, pero ese es el patrón de implementación general. Los detalles de cómo se envía el almacenamiento adicional y cómo se envían/obtienen difieren de un motor a otro, pero esto es lo más claro que puedo describir el diseño/implementación.

Un punto adicional menor, aunque la especificación ES se refiere a propertyNameuna cadena, los motores JS también tienden a especializarse en búsquedas de números enteros, por lo que someObject[someInteger]no convertirán el número entero en una cadena si está mirando un objeto que tiene propiedades de número entero, por ejemplo. Tipos de matriz, cadena y DOM ( NodeLists, etc.).

Mar 05 '2009 10:03 olliej