Colecciones ES6: ¿Es obligatoria la complejidad del tiempo lineal?

La especificación ES6 introduce colecciones con clave como Set, Map, WeakSet y WeakMap. Estas colecciones proporcionan formas eficientes de almacenar y recuperar datos basados ​​en claves. Sin embargo, surge la pregunta: ¿la especificación exige una complejidad de tiempo lineal para las operaciones en estas colecciones?

La complejidad del tiempo lineal o la elección de algoritmo quedan abiertas

A pesar de las expectativas de algoritmos de rendimiento ampliamente aceptados como el acceso O(1) para los prototipos Set y Map, la especificación ES6 sorprendentemente deja la puerta abierta a los algoritmos de tiempo lineal.

La especificación establece que "los objetos Set deben implementarse utilizando [mecanismos] que, en promedio, proporcionan tiempos de acceso sublineales". Se puede interpretar que este lenguaje incluye algoritmos de tiempo lineal. Sin embargo, no los exige explícitamente.

Del mismo modo, la especificación no descarta algoritmos de mayor rendimiento, como tablas hash o árboles equilibrados, que proporcionan una complejidad de tiempo logarítmica.

Ausencia de Mandatos de rendimiento explícitos

La ausencia de mandatos de rendimiento explícitos en la especificación ha llamado la atención entre los desarrolladores que esperaban que la especificación priorizara algoritmos rápidos.

Sin embargo, es importante tener en cuenta que el La especificación se centra en la semántica observable, como el orden de iteración predecible. Si bien se espera una implementación eficiente basada en hash, la especificación permite estructuras de datos alternativas como árboles, que ofrecen una complejidad de tiempo logarítmica.

Conclusión

La especificación ES6 no no exige explícitamente complejidad de tiempo lineal para operaciones en colecciones con clave. Si bien los algoritmos de tiempo lineal pueden observarse en algunas implementaciones, la especificación deja espacio para implementaciones de mayor rendimiento. Los desarrolladores deben consultar el navegador específico o la documentación del tiempo de ejecución para comprender la complejidad temporal real de estas operaciones de recopilación en diferentes contextos.