Javascript ES6 계산 / 시간 복잡성

Javascript ES6 계산 / 시간 복잡성

---

Keyed Collections (Set, Map, WeakSet 및 WeakMap)에 대한 ES6 사양에서 제공하는 시간 복잡성 (big-O 표기법)은 무엇입니까?

내 기대, 나는 대부분의 개발자로, 사양 및 구현을 사용하는 것입니다 것으로 예상 널리 인정 되는 경우에 성능이 좋은 알고리즘 Set.prototype.has, add그리고 delete평균 경우 모든 수 O (1)로한다. Map및 Weak–등가물에 대해서도 동일합니다 .

예를 들어 ECMAScript 2015 언어 사양-6th Edition — 23.2 Set Objects 에서 구현의 시간 복잡성이 의무화되었는지 여부는 나에게 완전히 분명하지 않습니다 .

내가 그것을 오해하지 않는 한 (그리고 확실히 내가 할 가능성이 매우 높다) ECMA 사양은 구현 (예 : Set.prototype.has선형 시간 ( O (n) )) 알고리즘 을 사용 하도록 요구하는 것으로 보입니다 . 더 많은 성능의 알고리즘이 사양에 의해 의무화되거나 허용되지 않는다는 것이 놀랍게도 놀라 울 것이며, 이것이 왜 그런지에 대한 설명에 매우 관심이있을 것입니다.

---

링크 된 바로 그 단락 에서 바로 :

집합 개체는 평균적으로 컬렉션의 요소 수에 하위 선형 인 액세스 시간을 제공하는 [메커니즘]을 사용하여 구현되어야합니다.

Maps , WeakMaps 및 WeakSets에 대해 동일한 문장을 찾을 수 있습니다.

ECMA 사양은 구현 (예 : Set.prototype.has)이 선형 시간 ( O(n)) 알고리즘 을 사용하도록 요구합니다 .

아니:

이 Set객체 사양에 사용 된 데이터 구조 는 Set 객체의 필수 관찰 가능한 의미를 설명하기위한 것입니다. 실행 가능한 구현 모델이 아닙니다.

관찰 가능한 의미 체계는 대부분 예측 가능한 반복 순서와 관련이 있습니다 (여전히 효율적이고 빠르게 구현할 수 있음 ). 구현이 해시 테이블 또는 일정한 액세스와 유사한 것을 사용하는 것이 실제로 사양에 의해 예상되지만 트리 (로그 액세스 복잡성 포함)도 허용됩니다.

---

궁금한 사람을 위해 매우 빠른 벤치 마크를 수행했습니다.

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

나는 이것을 몇 번 실행하고 다음과 같은 결과를 얻었습니다.

(2017 MacBook Pro, 2.5GHz i7 및 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

참고 URL : https://stackoverflow.com/questions/31091772/javascript-es6-computational-time-complexity-of-collections