¿Qué complejidad de tiempo (en notación O grande) proporciona la especificación ES6 para Keyed Collections (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 to all be O(1) en el caso promedio. Lo mismo para los equivalentes Map y Weak– .
No es del todo evidente para mí si la complejidad del tiempo de las implementaciones fue obligatoria, por ejemplo, en ECMAScript 2015 Language Specification - 6th Edition - 23.2 Set Objects .
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 ) usen un algoritmo de tiempo lineal ( O(n) ). Me sorprendería mucho que la especificación no exigiera o incluso permitiera algoritmos de mayor rendimiento, y estaría muy interesado en una explicación de por qué este es el caso.
Desde ese mismo párrafo está vinculado a:
Los objetos establecidos deben implementarse utilizando [mecanismos] que, en promedio, proporcionen tiempos de acceso que sean sublineales en la cantidad de elementos de la colección.
Encontrará la misma frase para Maps , WeakMaps y WeakSets .
Parece que la especificación ECMA exige que las implementaciones (por ejemplo, Set.prototype.has) usen un algoritmo de tiempo lineal (
O(n)).
No:
Las estructuras de datos utilizadas en esta especificación de objetos
Setsolo pretenden describir la semántica observable requerida de los objetos Set. No pretende ser un modelo de implementación viable.
La semántica observable está principalmente relacionada con el orden de iteración predecible (que aún puede implementarse 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).
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 arrojé los siguientes resultados:
(MacBook Pro 2017, 2,5 GHz i7 con 16 GB 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.515msLa pregunta es el método Set.has() O(1) y Array.indexOf O(n)? aparece como un duplicado de este, que no es exactamente (he votado para reabrir). Agregaré estos puntos de referencia aquí de todos modos, ya que los puntos de referencia en las respuestas a esa pregunta no muestran la gama completa de diferencias en el rendimiento entre Set#has y Array#indexOf .
Todo lo siguiente es cierto para Chrome 93:
Encuentra que para conjuntos de datos más pequeños, Array#indexOf en realidad supera a Set#has o Map#has ; sin embargo, para conjuntos de datos más grandes, Set#has y Map#has son varios órdenes de magnitud más rápidos. Lo cual es bastante consistente con lo que esperaría para las operaciones O(n) vs O(1).
Curiosamente, a pesar de que ambos son O(n), Array#includes es mucho más lento que Array#indexOf para un conjunto de datos pequeño, pero funciona de manera muy similar para conjuntos de datos grandes. Presumiblemente, Array#indexOf aprovecha alguna optimización que Array#includes no incluye.
Mientras tanto, Object#hasOwnProperty supera ligeramente a Set#has y Map#has en todos los casos (al menos en Chrome 93).
const [small, medium, large] = [1e3, 1e5, 1e7] const configs = [ { size: small, iterations: large }, { size: medium, iterations: medium }, { size: large, iterations: small }, ] for (const { size, iterations } of configs) { const arr = Array.from({ length: size }, (_, i) => String(i)) const obj = Object.fromEntries(arr.map(k => [k, true])) const set = new Set(arr) const map = new Map(Object.entries(obj)) const valsToTest = Array.from( { length: iterations }, (_, i) => String(Math.floor(Math.random() * size)), ) const title = `dataset size: ${size.toLocaleString()}; iterations: ${iterations.toLocaleString()}` console.log(`\n-> ${title}`) for (const [target, method] of [ [arr, 'indexOf'], [arr, 'includes'], [set, 'has'], [map, 'has'], [obj, 'hasOwnProperty'], ]) { const subtitle = `${target.constructor.name}#${method}` console.time(subtitle) for (const val of valsToTest) { target[method](val) } console.timeEnd(subtitle) } } -> dataset size: 1,000; iterations: 10,000,000 Array#indexOf: 185.100ms Array#includes: 11302.700ms Set#has: 367.400ms Map#has: 375.000ms Object#hasOwnProperty: 252.800ms -> dataset size: 100,000; iterations: 100,000 Array#indexOf: 10794.100ms Array#includes: 10476.800ms Set#has: 6.600ms Map#has: 6.800ms Object#hasOwnProperty: 1.900ms -> dataset size: 10,000,000; iterations: 1,000 Array#indexOf: 12798.900ms Array#includes: 12435.400ms Set#has: 0.800ms Map#has: 0.800ms Object#hasOwnProperty: 0.300ms