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

Javascript ES6 computational/time complexity of collections

本文关键字：时间复杂性 计算 ES6 集合 Javascript      更新时间：2023-09-26

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

我的期望，也是大多数开发人员的期望，是规范和实现将使用广泛接受的性能算法，在这种情况下，Set.prototype.has、add和delete在平均情况下都是O（1）。对于CCD_ 4和CCD_。

我并不完全清楚实现的时间复杂性是否是强制性的，例如在ECMAScript 2015语言规范-第6版-23.2 Set Objects中。

除非我误解了它（当然我也有可能误解），否则ECMA规范似乎要求实现（例如Set.prototype.has）使用线性时间（O（n））算法。更高性能的算法不会被规范强制甚至允许，这会让我感到非常惊讶，我很想解释为什么会出现这种情况。

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

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

对于Maps、WeakMaps和WeakSets，你会发现同样的句子。

看起来ECMA规范要求实现（例如Set.protype.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.5 GHz i7 w/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
问题是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在所有情况下都略优于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)
    }
}

我的结果（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
相关文章：