Javascript ES6 集合的计算/时间复杂性

javascript time-complexity ecmascript-6

2022-08-30 05:08:23

ES6 规范为键控集合（Set、Map、WeakSet 和 WeakMap）提供了什么时间复杂度（在 big-O 表示法中）？

我的期望，我期望大多数开发人员的期望是，规范和实现将使用广泛接受的高性能算法，在这种情况下，在一般情况下都是O（1）。和等效项也是如此。Set.prototype.hasadddeleteMapWeak–

对于我来说，实现的时间复杂度是否被强制要求并不完全清楚，例如在 ECMAScript 2015 语言规范 - 第 6 版 — 23.2 Set Objects 中。

除非我误解了它（我当然很有可能误解），否则看起来ECMA规范要求实现（例如Set.prototype.has）使用线性时间（O（n））算法。令我非常惊讶的是，规范不会强制要求甚至不允许更高性能的算法，而且我对解释为什么会这样非常感兴趣。

答案 1

从你链接到的那段话开始：

Set 对象必须使用 [机制] 实现，这些机制平均而言，这些机制提供的访问时间对集合中的元素数量是次线性的。

你会发现Maps，WeakMaps和WeakSets的句子相同。

看起来 ECMA 规范要求实现（例如 Set.prototype.has）使用线性时间（）算法。O(n)

不：

此 Set 对象规范中使用的数据结构仅用于描述 Set 对象所需的可观察语义。它不是一个可行的实现模型。

可观察的语义主要与可预测的迭代顺序有关（仍然可以高效快速地实现）。规范确实期望实现使用哈希表或类似的具有常量访问的东西，尽管树（具有对数访问复杂性）也是允许的。

答案 2

对于任何好奇的人，我做了一个非常快速的基准测试：

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.5 GHz i7 带 16G 内存）

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