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

Question

当谈到javascript中的集合与数组时，我一直在阅读关于现代javascript引擎的时间复杂性的相互矛盾的答案。

我完成了codility的演示任务，这是一个简单的任务，可以找到以下问题的解决方案：给定一个由N个整数组成的数组a，返回a中没有出现的最小正整数(大于0(。

例如，给定A=[1，3，6，4，1，2]，函数应该返回5。

我的第一个解决方案是：

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

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

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

const solution = arr => {
const set = new Set(arr);
let i = 1;
while (set.has(i)) {
i++;
}
return i;
}

Codibility表示，这显然具有O(N(或O(N*log(N((的时间复杂性。

这是正确的吗？array.prototype.in实际上包含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);

如果集合查找具有更好的时间复杂度(如果这是真的(，并且是可编码性的首选，为什么我的性能测试支持array.prototype.includes解决方案？

Answer 1

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

从经验上讲，当我在一些代码游戏中运行Set.has时，它表现出了线性性能。。。但在node和chrome这样的真实环境中，它们并不令人意外。我不确定操场的后端是什么，但可能使用了Set polyfill。所以要小心！

以下是我的测试用例，经过裁剪以消除随机性：

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

所以，是的，数组是线性的，集合要快得多。

Answer 2

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

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

您可能会注意到，对于小数组，Set可能会慢一些。这是微不足道的，因为时间复杂性只会对大的(重要的(n产生影响。

还要注意，Array.includes确实是O(n(，但因为它在for循环中，在最坏的情况下可能会上升到n，所以解决方案的时间复杂度为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));