Big O de los arreglos de JavaScript

Los arrays en JavaScript son muy fáciles de modificar agregando y eliminando elementos. Esto en cierto modo enmascara el hecho de que los arrays en la mayoría de los lenguajes tienen tamaño fijo y requieren operaciones complejas para cambiar su tamaño. Parece que JavaScript facilita escribir código de arrays con bajo rendimiento. Esto lleva a la pregunta:

¿Qué rendimiento (en términos de complejidad temporal de big O) puedo esperar de las implementaciones de JavaScript con respecto al rendimiento de los arrays?

Supongo que todas las implementaciones razonables de JavaScript tienen como máximo los siguientes órdenes de magnitud O.

• Acceso - O(1)
• Añadiendo - O(n)
• Prependiendo - O(n)
• Inserción - O(n)
• Eliminación - O(n)
• Intercambio - O(1)

JavaScript te permite rellenar previamente un arreglo hasta un cierto tamaño, usando la sintaxis new Array(length). (Pregunta extra: ¿Es crear un arreglo de esta manera O(1) o O(n)?) Esto es más parecido a un arreglo convencional, y si se usa como un arreglo de tamaño predefinido, puede permitir agregar elementos al final en O(1). Si se añade lógica de buffer circular, puedes lograr agregar elementos al inicio en O(1). Si se usa un arreglo que se expande dinámicamente, O(log n) será el caso promedio para ambos.

¿Puedo esperar un mejor rendimiento en algunas cosas que mis suposiciones aquí? No espero que algo esté detallado en ninguna especificación, pero en la práctica, podría ser que todas las implementaciones principales usen arrays optimizados detrás de escena. ¿Hay arrays que se expanden dinámicamente u otros algoritmos que aumenten el rendimiento en funcionamiento?

P.D.

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

Respuesta #1

_{NOTA: Aunque esta respuesta era correcta en 2012, los motores utilizan representaciones internas muy diferentes tanto para objetos como para arreglos hoy en día. Esta respuesta puede o no ser verdadera.}

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

• Acceso - O(1)
• Agregar - O(1) amortizado (a veces se requiere redimensionar la tabla hash; usualmente solo se requiere inserción)
• Agregar al principio - O(n) a través de unshift, ya que requiere reasignar todos los índices
• Inserción - O(1) amortizado si el valor no existe. O(n) si deseas desplazar valores existentes (por ejemplo, usando splice).
• Eliminación - Amortizado O(1) para eliminar un valor, O(n) si deseas reasignar índices mediante splice.
• Intercambio - O(1)

En general, establecer o desestabler cualquier clave en un diccionario es O(1) amortizado, y lo mismo ocurre con los arreglos, sin importar cuál sea el índice. Cualquier operación que requiera renumerar valores existentes es O(n) simplemente porque tienes que actualizar todos los valores afectados.

Respuesta #2

garantía

No hay una garantía de complejidad temporal especificada para ninguna operación de arreglo. El rendimiento de los arreglos depende de la estructura de datos subyacente que el motor elija. Los motores también pueden tener diferentes representaciones y cambiar entre ellas según ciertas heurísticas. El tamaño inicial del arreglo puede o no ser tal heurística.

realidad

Por ejemplo, V8 utiliza (hasta hoy) tanto tablas hash como listas de arreglos para representar arreglos. También tiene diversas representaciones diferentes para objetos, por lo que los arreglos y los objetos no pueden compararse. Por lo tanto, el acceso a un arreglo siempre es mejor que O(n), y podría incluso ser tan rápido como el acceso a un arreglo en C++. Agregar al final es O(1), a menos que se alcance el tamaño de la estructura de datos y tenga que ser escalada (lo cual es O(n)). Agregar al inicio es peor. La eliminación puede ser incluso peor si haces algo como delete array[index] (¡no lo hagas!), ya que eso podría obligar al motor a cambiar su representación.

consejo

Usa arrays para estructuras de datos numéricas. Para eso están hechos. Para eso los optimizarán los motores. Evita arrays dispersos (o si tienes que usarlos, espera un rendimiento peor). Evita arrays con tipos de datos mixtos (ya que eso hace que las representaciones internas sean más complejas).

Si realmente quieres optimizar para un motor (y versión) en particular, revisa su código fuente para obtener la respuesta absoluta.