latest - json array javascript

Gran O de arreglos de JavaScript

Question

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

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

Supongo que todas las implementaciones razonables de JavaScript tienen al menos las siguientes O grandes.

• Acceso - O (1)
• Anexando - O (n)
• Anteponiendo - O (n)
• Inserción - O (n)
• Eliminación - O (n)
• Intercambio - O (1)

JavaScript le permite completar previamente una matriz con un determinado tamaño, utilizando la new Array(length) sintaxis de la new Array(length) . (Pregunta de bonificación: está creando una matriz de esta manera O (1) u O (n)) Esto es más parecido a una matriz convencional, y si se usa como una matriz pre-dimensionada, puede permitir la adición de O (1). Si se agrega una lógica de búfer circular, puede lograr O (1) antepuesto. Si se utiliza una matriz que se expande dinámicamente, 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 ninguna especificación, pero en la práctica podría ser que todas las implementaciones principales usen matrices optimizadas entre bastidores. ¿Existen matrices que se expanden dinámicamente o algunos otros algoritmos para aumentar el rendimiento en funcionamiento?

PD

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

Answer 1

A diferencia de la mayoría de los lenguajes, que implementan matrices con matrices, en Javascript Las matrices son objetos y los valores se almacenan en una tabla hash, al igual que los valores de objeto regulares. 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)
• Anteponiendo - O (n) a través de 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, utilizando splice ).
• Eliminación - Amortizado O (1) para eliminar un valor, O (n) si desea reasignar índices mediante splice .
• Intercambio - O (1)

En general, la configuración o desconexión de cualquier tecla 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.

Answer 2

Todas las complejidades que mencionas parecen estar bien. Pero si el objeto de matriz mantiene la longitud, el anexar también se puede hacer en O (1) vez.