Javascript ES6 złożoność obliczeniowa / czasowa zbiorów

Jaką złożoność czasową (w notacji duże-O) zapewnia specyfikacja ES6 dla kolekcji z kluczem (Set, Map, WeakSet i WeakMap)?

Oczekuję, i spodziewam się tego od większości programistów, że specyfikacje i implementacje będą używać powszechnie akceptowanych algorytmów wydajności, w którym to przypadku Set.prototype.has, addi deletewszystkie będą O (1) w przeciętnym przypadku. To samo dotyczy Mapi Weak–odpowiedników.

Nie do końca jest dla mnie jasne, czy złożoność czasowa implementacji była wymagana np. W specyfikacji języka ECMAScript 2015 - wydanie 6 - 23.2 Ustaw obiekty .

O ile nie zrozumiem tego źle (a na pewno jest to bardzo możliwe), wygląda na to, że specyfikacja ECMA nakazuje, aby implementacje (np. Set.prototype.has) Używały algorytmu czasu liniowego ( O (n) ). Wydałoby mi się niezwykle zaskakujące, że bardziej wydajne algorytmy nie byłyby wymagane lub nawet dozwolone w specyfikacji, i byłbym bardzo zainteresowany wyjaśnieniem, dlaczego tak się dzieje.

Od tego samego akapitu, do którego linkujesz:

Obiekty zestawu muszą być implementowane przy użyciu [mechanizmów], które średnio zapewniają czasy dostępu, które są podliniowe względem liczby elementów w kolekcji.

To samo zdanie znajdziesz dla Map , WeakMaps i WeakSets .

Wygląda na to, że specyfikacja ECMA nakazuje, aby implementacje (np. Set.prototype.has) używały liniowego O(n)algorytmu time ( ).

Nie:

Struktury danych użyte w tej Setspecyfikacji obiektów mają na celu jedynie opisanie wymaganej obserwowalnej semantyki obiektów Set. Nie ma to być realny model wdrażania.

Obserwowalna semantyka jest głównie związana z przewidywalną kolejnością iteracji (która nadal może być wdrożona wydajnie i szybko ). Rzeczywiście, specyfikacja przewiduje, że implementacja używa tablicy mieszającej lub czegoś podobnego ze stałym dostępem, chociaż drzewa (o logarytmicznej złożoności dostępu) są również dozwolone.

Dla każdego, kto jest ciekawy, zrobiłem bardzo szybki test porównawczy:

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

Uruchomiłem to kilka razy i uzyskałem następujące wyniki:

(2017 MacBook Pro, 2,5 GHz i7 z 16G 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