Javascript ES6 computational/time 集合的复杂度

Question

ES6 规范为键控集合（Set、Map、WeakSet 和 WeakMap）提供了多少时间复杂度（以大 O 表示法表示）？

我和大多数开发人员的期望是规范和实现将使用 widely accepted 高性能算法，在这种情况下 Set.prototype.has、add 和 delete 在平均情况下都是 O(1)。 Map 和 Weak– 等价物也是如此。

我不太清楚实施的时间复杂度是否是强制性的，例如在 ECMAScript 2015 Language Specification - 6th Edition — 23.2 Set Objects.

除非我误解了它（而且我确实很有可能这样做），看起来 ECMA 规范要求实现（例如 Set.prototype.has）要使用线性时间（O( n))算法。如果规范不强制甚至允许更高性能的算法，我会感到非常惊讶，我很想知道为什么会这样。

Answer 1

来自 that very paragraph 您的链接到：

Set objects must be implemented using [mechanisms] that, on average, provide access times that are sublinear on the number of elements in the collection.

您会发现 Maps, WeakMaps and WeakSets 的相同句子。

It looks the ECMA spec mandates that the implementations (e.g. Set.prototype.has) are to use a linear time (O(n)) algorithm.

否：

The data structures used in this Set objects specification is only intended to describe the required observable semantics of Set objects. It is not intended to be a viable implementation model.

可观察的语义主要与谓词table迭代顺序有关（仍然可以是implemented efficient and fast）。规范确实期望实现使用散列 table 或类似的具有常量访问的东西，尽管树（具有对数访问复杂性）也被允许。

Answer 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

Answer 3

问题被列为该问题的副本，但并不完全相同（我已投票决定重新打开）。无论如何，我都会在这里添加这些基准，因为对该问题的答复中的基准无法显示 Set#has 和 Array#indexOf.

之间的全部性能差异。

以下对Chrome93都是正确的：

您发现对于较小的数据集，Array#indexOf 实际上优于 Set#has 或 Map#has；然而，对于更大的数据集，Set#has 和 Map#has 的速度快了多个数量级。这与您对 O(n) 与 O(1) 操作的期望非常一致。

有趣的是，尽管两者都是 O(n)，Array#includes 对于小型数据集比 Array#indexOf 慢得多，但对于大型数据集的表现非常相似。据推测，Array#indexOf 利用了一些 Array#includes 没有的优化。

同时，Object#hasOwnProperty 在所有情况下都略优于 Set#has 和 Map#has（至少在 Chrome 93）。

基准代码

const [small, medium, large] = [1e3, 1e5, 1e7]

const configs = [
    { size: small, iterations: large },
    { size: medium, iterations: medium },
    { size: large, iterations: small },
]

for (const { size, iterations } of configs) {
    const arr = Array.from({ length: size }, (_, i) => String(i))
    const obj = Object.fromEntries(arr.map(k => [k, true]))
    const set = new Set(arr)
    const map = new Map(Object.entries(obj))

    const valsToTest = Array.from(
        { length: iterations },
        (_, i) => String(Math.floor(Math.random() * size)),
    )

    const title = `dataset size: ${size.toLocaleString()}; iterations: ${iterations.toLocaleString()}`

    console.log(`\n-> ${title}`)

    for (const [target, method] of [
        [arr, 'indexOf'],
        [arr, 'includes'],
        [set, 'has'],
        [map, 'has'],
        [obj, 'hasOwnProperty'],
    ]) {
        const subtitle = `${target.constructor.name}#${method}`

        console.time(subtitle)

        for (const val of valsToTest) {
            target[method](val)
        }

        console.timeEnd(subtitle)
    }
}

我的成绩（Chrome93）


-> dataset size: 1,000; iterations: 10,000,000
Array#indexOf: 185.100ms
Array#includes: 11302.700ms
Set#has: 367.400ms
Map#has: 375.000ms
Object#hasOwnProperty: 252.800ms

-> dataset size: 100,000; iterations: 100,000
Array#indexOf: 10794.100ms
Array#includes: 10476.800ms
Set#has: 6.600ms
Map#has: 6.800ms
Object#hasOwnProperty: 1.900ms

-> dataset size: 10,000,000; iterations: 1,000
Array#indexOf: 12798.900ms
Array#includes: 12435.400ms
Set#has: 0.800ms
Map#has: 0.800ms
Object#hasOwnProperty: 0.300ms

Javascript ES6 computational/time 集合的复杂度

Javascript ES6 computational/time complexity of collections

javascript

time-complexity

ecmascript-6

基准代码

我的成绩（Chrome93）