¿Qué complejidad de tiempo (en notación O grande) proporciona la especificación ES6 para las colecciones con clave (Set, Map, WeakSet y WeakMap)?
Mi expectativa, y la de la mayoría de los desarrolladores, es que las especificaciones y las implementaciones utilicen algoritmos de rendimiento ampliamente aceptados , en cuyo caso Set.prototype.has
, add
y delete
todos sean O (1) en el caso promedio. Lo mismo para los Map
y Weak–
equivalentes.
No me resulta del todo evidente si la complejidad temporal de las implementaciones fue obligatoria, por ejemplo, en la Especificación del lenguaje ECMAScript 2015 - 6ª edición - 23.2 Establecer objetos .
A menos que lo entienda mal (y ciertamente es muy posible que lo haga), parece que la especificación ECMA exige que las implementaciones (por ejemplo Set.prototype.has
) deben usar un algoritmo de tiempo lineal ( O (n) ). Me parecería sumamente sorprendente que la especificación no exigiera o incluso permitiera algoritmos más eficaces, y estaría muy interesado en una explicación de por qué este es el caso.
fuente
Respuestas:
Desde ese mismo párrafo estás vinculado a:
Encontrará la misma oración para Maps , WeakMaps y WeakSets .
No:
La semántica observable está relacionada principalmente con el orden de iteración predecible (que aún se puede implementar de manera eficiente y rápida ). De hecho, la especificación espera que una implementación use una tabla hash o algo similar con acceso constante, aunque también se permiten árboles (con complejidad de acceso logarítmico).
fuente
Para cualquiera que tenga curiosidad, hice un punto de referencia muy rápido:
const benchmarkMap = size => { console.time('benchmarkMap'); var map = new Map(); for (var i = 0; i < size; i++) map.set(i, i); for (var i = 0; i < size; i++) var x = map.get(i); console.timeEnd('benchmarkMap'); } const benchmarkObj = size => { console.time('benchmarkObj'); var obj = {}; for (var i = 0; i < size; i++) obj[i] = i; for (var i = 0; i < size; i++) var x = obj[i]; console.timeEnd('benchmarkObj'); } var size = 1000000; benchmarkMap(size); benchmarkObj(size);
Ejecuté esto varias veces y obtuve los siguientes resultados:
(MacBook Pro 2017, i7 de 2,5 GHz con 16 G de RAM)
benchmarkMap: 189.120ms benchmarkObj: 44.214ms benchmarkMap: 200.817ms benchmarkObj: 38.963ms benchmarkMap: 187.968ms benchmarkObj: 41.633ms benchmarkMap: 186.533ms benchmarkObj: 35.850ms benchmarkMap: 187.339ms benchmarkObj: 44.515ms
fuente
delete
operaciones y operaciones se entremezclan,Map
funciona mucho mejor. jsfiddle.net/23hrp0eq