[javascript] Javascript ES6 계산 / 시간 복잡성

Program / 글쓴이

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

답변