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

Question

密钥集合(Set,Map,WeakSet和WeakMap)的ES6规范提供了什么时间复杂度(以大O表示法)？

我的期望,并且我希望大多数开发人员都希望,规范和实现将使用广泛接受的性能算法,在这种情况下Set.prototype.has,add并且delete在一般情况下都是O(1).相同的Map和Weak–等价物.

对于我来说,实现的时间复杂性是否是强制性的,例如在ECMAScript 2015语言规范 - 第6版 - 23.2设置对象中,这一点并不完全清楚.

除非我误解它(我当然很可能),看起来ECMA规范要求实现(例如Set.prototype.has)使用线性时间(O(n))算法.令我非常惊讶的是,规范中不会强制要求甚至不允许使用更高性能的算法,我会对为什么会出现这种情况的解释非常感兴趣.

Answer 1

从那段链接到你的链接:

必须使用[机制]来实现集合对象,这些机制平均提供对集合中元素数量的次线性访问时间.

您将找到Maps,WeakMaps和WeakSets的相同句子.

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

没有:

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

可观察的语义主要与可预测的迭代顺序相关(它仍然可以高效且快速地实现).规范确实期望实现使用散列表或类似于常量访问的东西,尽管也允许树(具有对数访问复杂性).

Answer 2

问题是 Set.has() 方法 O(1) 和 Array.indexOf O(n) 吗？被列为与此重复，但事实并非如此（我已投票决定重新开放）。Set#has无论如何，我都会在这里添加这些基准，因为对该问题的答复的基准未能显示和之间性能的全部差异Array#indexOf。

以下内容均适用于 Chrome 93：

您发现，对于较小的数据集，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都略微优于（至少在 Chrome 93 中）。Set#hasMap#has

基准测试代码

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

我的结果（Chrome 93）

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

Answer 3

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

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