Complejidad computacional / temporal de colecciones de Javascript ES6

84

¿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, addy deletetodos sean O (1) en el caso promedio. Lo mismo para los Mapy 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.

Brian M. Hunt
fuente
2
Todos los algoritmos O (1) también son O (n) , por lo que permitir implementaciones de menor rendimiento no hace ningún daño. Probablemente, las implementaciones de menor rendimiento pueden ser de algún interés en sistemas con recursos limitados, ya que lo más probable es que requieran mucho menos código / espacio.
artur grzesiak
@arturgrzesiak El rendimiento O (1) de las colecciones con clave se logra generalmente con un hash O (1) más un depósito de colisión O (n). El peor de los casos O (n) es astronómicamente raro para la mayoría de los propósitos prácticos. La complejidad espacial de estas técnicas es generalmente O (n).
Brian M. Hunt
1
"Los objetos de conjunto deben implementarse utilizando tablas hash u otros mecanismos que, en promedio, proporcionan tiempos de acceso que son sublineales en el número de elementos de la colección".
georg

Respuestas:

59

Desde ese mismo párrafo estás vinculado a:

Los objetos de conjunto deben implementarse utilizando [mecanismos] que, en promedio, proporcionen tiempos de acceso que son sublineales en el número de elementos de la colección.

Encontrará la misma oración para Maps , WeakMaps y WeakSets .

Parece que la especificación ECMA exige que las implementaciones (por ejemplo, Set.prototype.has) utilicen un O(n)algoritmo de tiempo lineal ( ).

No:

Las estructuras de datos utilizadas en esta Setespecificación de objetos solo están destinadas a describir la semántica observable requerida de los objetos Set. No pretende ser un modelo de implementación viable.

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).

Bergi
fuente
2
Gracias por elegir eso. Mis ojos debieron de estar vidriosos cuando llegué a ese párrafo. :) Entonces, ¿algoritmos que son O (log (n)) u O (1), pero que no son obligatorios (siempre que estén bajo O (n))?
Brian M. Hunt
1
@ BrianM.Hunt: Correcto.
Bergi
31

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
domdambrogia
fuente
3
@domdambrogia si separa la configuración de obtener I get: Map Set = 124, Map Get = 40, Object Set = 26, Object Get = 1 (estas son proporciones, no ms)
AJP
@AJP No pensé en desglosarlo también con esas estadísticas. Gracias por tu aporte, esa es una buena contribución. Veré si puedo agregar eso a mi respuesta cuando tenga un segundo. ¡Gracias!
domdambrogia
Sería interesante separar la tarea de la lectura para saber también cuál de las dos es más rápida para leer.
fernandopasik
3
" MacBook Pro 2017, i7 de 2.5 GHz con 16G de RAM " - uh, eso es genial y todo, pero ¿ qué motor de javascript evaluó?
Bergi
1
Curiosamente, cuando se agregan deleteoperaciones y operaciones se entremezclan, Mapfunciona mucho mejor. jsfiddle.net/23hrp0eq
Jorjon