Gran O de matrices de JavaScript

Las matrices en JavaScript son muy fáciles de modificar agregando y eliminando elementos. De alguna manera enmascara el hecho de que la mayoría de las matrices de idiomas son de tamaño fijo y requieren operaciones complejas para cambiar su tamaño. Parece que JavaScript facilita la escritura de código de matriz de bajo rendimiento. Esto lleva a la pregunta:

¿Qué rendimiento (en términos de gran complejidad de tiempo O) puedo esperar de las implementaciones de JavaScript con respecto al rendimiento de la matriz?

Supongo que todas las implementaciones de JavaScript razonables tienen como máximo las siguientes O grandes.

• Acceso - O (1)
• Anexando - O (n)
• Anteponer - O (n)
• Inserción - O (n)
• Supresión - O (n)
• Intercambio - O (1)

JavaScript le permite rellenar previamente una matriz a un cierto tamaño, utilizando new Array(length)sintaxis. (Pregunta adicional: ¿Está creando una matriz de esta manera O (1) u O (n)) Esto es más como una matriz convencional, y si se usa como una matriz de tamaño predeterminado, puede permitir que se agregue O (1). Si se agrega lógica de búfer circular, puede lograr O (1) anteponer. Si se usa una matriz de expansión dinámica, O (log n) será el caso promedio para ambos.

¿Puedo esperar un mejor rendimiento para algunas cosas que mis suposiciones aquí? No espero que se describa nada en las especificaciones, pero en la práctica, podría ser que todas las implementaciones principales usen arreglos optimizados detrás de escena. ¿Hay matrices que se expanden dinámicamente u otros algoritmos que mejoran el rendimiento en funcionamiento?

PD

La razón por la que me pregunto esto es que estoy investigando algunos algoritmos de clasificación, la mayoría de los cuales parecen asumir que agregar y eliminar son operaciones O (1) al describir su gran O general.

_{NOTA: Si bien esta respuesta fue correcta en 2012, los motores utilizan representaciones internas muy diferentes para objetos y matrices en la actualidad. Esta respuesta puede ser cierta o no.}

A diferencia de la mayoría de los lenguajes, que implementan matrices con, bueno, matrices, en Javascript las matrices son objetos y los valores se almacenan en una tabla hash, al igual que los valores de objetos normales. Como tal:

• Acceso - O (1)
• Anexar - Amortizado O (1) (a veces se requiere cambiar el tamaño de la tabla hash; generalmente solo se requiere inserción)
• Anteponer - O (n) via unshift, ya que requiere reasignar todos los índices
• Inserción - Amortizado O (1) si el valor no existe. O (n) si desea cambiar los valores existentes (por ejemplo, usando splice).
• Eliminación: O (1) amortizado para eliminar un valor, O (n) si desea reasignar índices a través de splice.
• Intercambio - O (1)

En general, activar o desactivar cualquier clave en un dict se amortiza O (1), y lo mismo ocurre con las matrices, independientemente de cuál sea el índice. Cualquier operación que requiera volver a numerar los valores existentes es O (n) simplemente porque tiene que actualizar todos los valores afectados.

garantía

No existe una garantía de complejidad de tiempo especificada para ninguna operación de matriz. El rendimiento de las matrices depende de la estructura de datos subyacente que elija el motor. Los motores también pueden tener diferentes representaciones y cambiar entre ellas en función de determinadas heurísticas. El tamaño de la matriz inicial puede ser o no una heurística.

realidad

Por ejemplo, V8 usa (a partir de hoy) tanto tablas hash como listas de matrices para representar matrices. También tiene varias representaciones diferentes de objetos, por lo que no se pueden comparar matrices y objetos. Por lo tanto, el acceso a la matriz siempre es mejor que O (n), e incluso puede ser tan rápido como un acceso a la matriz de C ++. Agregar es O (1), a menos que alcance el tamaño de la estructura de datos y tenga que escalarla (que es O (n)). Pretender es peor. La eliminación puede ser incluso peor si hace algo como delete array[index](¡no lo haga!), Ya que eso podría obligar al motor a cambiar su representación.

Consejo

Utilice matrices para estructuras de datos numéricas. Para eso están destinados. Para eso los optimizarán los motores. Evite las matrices dispersas (o, si es necesario, espere un peor rendimiento). Evite las matrices con tipos de datos mixtos (ya que eso hace que las representaciones internas sean más complejas ).

Si realmente desea optimizar para un determinado motor (y versión), verifique su código fuente para obtener la respuesta absoluta.