ordenar - metodos de busqueda javascript

Javascript ES6 complejidad computacional/de tiempo de colecciones

Question

¿Qué complejidad de tiempo (en notación big-O) proporciona la especificación ES6 para las colecciones con clave (Set, Map, WeakSet y WeakMap)?

Mi expectativa, y espero que la de la mayoría de los desarrolladores, es que las especificaciones e implementaciones usarían algoritmos de rendimiento ampliamente aceptados , en cuyo caso Set.prototype.has , add y delete para que todos sean O (1) en el caso promedio. Lo mismo para el Map y los Weak– equivalentes.

No es del todo evidente para mí si la complejidad temporal de las implementaciones fue obligatoria, por ejemplo, en ECMAScript 2015 Language Specification - 6th Edition - 23.2 Set Objects .

A menos que lo malinterprete (y ciertamente es muy posible que lo haga), parece que las especificaciones de ECMA Set.prototype.has que las implementaciones (por ejemplo, Set.prototype.has ) utilicen un algoritmo de tiempo lineal ( O (n) ). Me parecería extremadamente sorprendente que los algoritmos más efectivos no fueran obligatorios o incluso permitidos por la especificación, y me interesaría mucho una explicación de por qué este es el caso.

Answer 1

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

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

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

Parece que las especificaciones de ECMA exigen que las implementaciones (por ejemplo, Set.prototype.has) utilicen un algoritmo de tiempo lineal ( O(n) ).

No:

Las estructuras de datos utilizadas en esta especificación de objetos Set 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 los árboles (con complejidad de acceso logarítmico) también están permitidos.

Answer 2

Para cualquiera que sea curioso, 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 algunas veces y obtuve los siguientes resultados:

(2017 MacBook Pro, 2.5 GHz i7 con 16G RAM)

benchmarkMap: 189.120ms
benchmarkHash: 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