array.prototype.includes 与 set.prototype.has 的时间复杂度

Question

我一直在阅读有关现代 javascript 引擎在集合与数组方面的时间复杂度的相互矛盾的答案 javascript。

我完成了 codility 的演示任务，这是一个简单的作业，用于找到以下问题的解决方案：给定一个包含 N 个整数的数组 A，return 满足以下条件的最小正整数（大于 0）不会出现在 A.

例如，给定 A = [1, 3, 6, 4, 1, 2]，函数应该 return 5.

我的第一个解决方案是：

const solution = arr => {
    for(let int = 1;;int++) {
        if (!arr.includes(int)) {
            return int;
        }
    }
}

现在，奇怪的是 codility 说这个解决方案的时间复杂度为 O(n**2)（他们更喜欢复杂度为 O(n) 的解决方案）。据我所知，array.prototype.includes 是线性搜索 (https://tc39.es/ecma262/#sec-array.prototype.includes)，这意味着它应该具有 O(n) 时间复杂度。

如果我输入不同的解决方案，使用 Set，我会得到满分：

const solution = arr => {
  const set = new Set(arr);
  let i = 1;

  while (set.has(i)) {
    i++;
  }

  return i;
}

Codility 说这显然具有 O(N) 或 O(N * log(N)) 的时间复杂度。

这是正确的吗？ array.prototype.includes 实际上是 O(n**2) 而不是 O(n)？

最后，我有点困惑为什么 Set.has() 在我的控制台性能测试中是首选，Array.includes() 始终优于首先创建 Set 和然后在场景中查找它，如以下代码片段所示。

const rand = (size) => [...Array(size)].map(() => Math.floor(Math.random() * size));

const small = rand(100);
const medium = rand(5000);
const large = rand(100000);

const solution1 = arr => {
  console.time('Array.includes');
  for(let int = 1;;int++) {
    if (!arr.includes(int)) {
      console.timeEnd('Array.includes');
      return int;
    }
  }
}

const solution2 = arr => {
  console.time('Set.has');
  const set = new Set(arr);
  let i = 1;
  while (set.has(i)) {
    i++;
  }
  console.timeEnd('Set.has');
  return i;
}

console.log('Testing small array:');
solution1(small);
solution2(small);
console.log('Testing medium array:');
solution1(medium);
solution2(medium);
console.log('Testing large array:');
solution1(large);
solution2(large);

如果集合查找具有更好的时间复杂度（如果这是真的）并且是 codility 的首选，为什么我的性能测试有利于 array.prototype.includes 解决方案？

Answer 1

这样的比较并不完全公平，因为在使用Set的函数中，需要先将Array转换为Set，这需要一些时间。

如果忽略此项，请查看下面的结果。我更新了 solution2 函数以接收 Set 并将 while 循环更改为 for 循环 - 为了直接比较。

您可能会注意到对于小数组，Set 可能会更慢。这是微不足道的，因为时间复杂度只会真正影响到一个大的（重要的）n。

另请注意，Array.includes 确实是 O(n)，但因为它处于 for 循环中，在最坏的情况下可能会达到 n solution 的时间复杂度为 O(n^2).

const rand = (size) => [...Array(size)].map(() => Math.floor(Math.random() * size));

const small = rand(100);
const medium = rand(5000);
const large = rand(100000);

const solution1 = arr => {
  console.time('Array.includes');
  for (let int = 1;;int++) {
    if (!arr.includes(int)) {
      console.timeEnd('Array.includes');
      return int;
    }
  }
}

const solution2 = set => {
  console.time('Set.has');
  for (let i = 1;;i++) {
    if (!set.has(i)) {
      console.timeEnd('Set.has');
      return i
    }
  }
}

console.log('Testing small array:');
solution1(small);
solution2(new Set(small));
console.log('Testing medium array:');
solution1(medium);
solution2(new Set(medium));
console.log('Testing large array:');
solution1(large);
solution2(new Set(large));

Answer 2

我知道这是一个老问题，但我仔细检查了数据。我也假设 Set.has 将是 O(1) 或 O(log N)，但在我的第一次测试中，它似乎是 O(N)。这些函数的规范暗示很多，但很难破译：https://tc39.es/ecma262/#sec-array.prototype.includes https://tc39.es/ecma262/#sec-set.prototype.has 不过，在其他地方，他们还说 Set.has 必须是次线性的——我相信现代实现是。

根据经验，Set.has 在某些代码游乐场中运行表现出线性性能......但在像 node 和 chrome 这样的真实环境中，它们并不令人惊讶。我不确定后端的 playground 运行是什么，但也许使用了 Set polyfill。所以要小心！

这里是 my test cases，经过修剪以去除运行domness：

const makeArray = (size) => [...Array(size)].map(() => size);

const small =  makeArray(1000000);
const medium = makeArray(10000000);
const large =  makeArray(100000000);

const solution1 = arr => {
  console.time('Array.includes');
  arr.includes(arr.length - 1)
  console.timeEnd('Array.includes');
}

const solution2 = arr => {
  const set = new Set(arr)
  console.time('Set.has');
  set.has(arr.length-1)
  console.timeEnd('Set.has');
}


console.log('** Testing small array:');
solution1(small);
solution2(small);
console.log('** Testing medium array:');
solution1(medium);
solution2(medium);
console.log('** Testing large array:');
solution1(large);
solution2(large);

在Chrome中，虽然：

** Testing small array:
VM183:10 Array.includes: 1.371826171875 ms
VM183:17 Set.has: 0.005859375 ms
VM183:25 ** Testing medium array:
VM183:10 Array.includes: 14.32568359375 ms
VM183:17 Set.has: 0.009765625 ms
VM183:28 ** Testing large array:
VM183:10 Array.includes: 115.695068359375 ms
VM183:17 Set.has: 0.0048828125 ms

在节点 16.5 中：

Testing small array:
Array.includes: 1.223ms
Set.has: 0.01ms
Testing medium array:
Array.includes: 11.41ms
Set.has: 0.054ms
Testing large array:
Array.includes: 127.297ms
Set.has: 0.047ms

所以，是的，数组在定义上是线性的，而集合要快得多。

array.prototype.includes 与 set.prototype.has 的时间复杂度

Time complexity of array.prototype.includes vs. set.prototype.has

javascript

arrays

performance

set

time-complexity