Javascript big-O rendimiento de acceso a la propiedad

Question

¿Cuáles son las características de rendimiento del acceso a la propiedad de JavaScript (en las implementaciones actuales)?

• ¿Es seguro asumir que el acceso a la matriz es O (1)?

• Si uso un objeto como una tabla hash (con claves de cadena) ¿puedo asumir con seguridad O (1) u O (log n) el tiempo de acceso?

• ¿Hay navegadores o ambientes que son significativamente más rápido/lento que los demás comunes y que debería mantener un ojo para?

• ¿Los estándares de JavaScript tienen algo que decir?

Y lo más importante:

• ¿Dónde puedo encontrar una buena referencia para este tipo de problemas de rendimiento de JavaScript asintótica?

Answer 1

Todos los objetos en JavaScript se implementan como un hash de objeto, por lo que no existe una diferencia funcional.

Por ejemplo, visita esta prueba:

var arr = []; 
arr[5] = 5; 
arr['5'] = 'not 5'; 
console.log(arr.length, arr); 
// output: 6 [undefined, undefined, undefined, undefined, undefined, "not 5"] 

Los números se stringified cuando se utiliza como posiciones.

Ver Crockford's website sobre JavaScript para obtener más información. La parte es especialmente importante en el epígrafe de "conjuntos":

Arrays in JavaScript are also hashtable objects.

rendimiento no es realmente un problema a menos que tenga un montón de objetos para realizar un seguimiento de los (como más de 500.000), en cuyo caso' Probablemente esté haciendo algo mal.

Hay optimizaciones que puede hacer, pero en realidad no tienen sentido a menos que esté haciendo algo antinatural con JavaScript (como algoritmos de compresión ... Trabajé en una implementación de LZMA en JS ... mala idea).

Nota:

Si usted tiene un juego de repuesto (como se define sólo 10 índices de cada 10.000), probablemente debería ser el uso de un objeto de regular. Las matrices inicializarán los 10 000 índices en "indefinido", mientras que Object.keys(obj) solo informarán los 10 que ha establecido. Esta es una optimización menor que realmente tiene sentido.