当涉及到 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) (他们更喜欢复杂度为 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 解决方案?
我知道这是一个老问题,但我仔细检查了数据。我也假设
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
展示了线性性能......但在节点和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
所以,是的,数组绝对是线性的,而集合要快得多。
这样的比较并不完全公平,因为在使用 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));
我做了 leetcode 问题 Contains Duplicates,你必须检查给定的数字数组中是否有重复项。 我提交了两个解决方案:
.has()
方法function containsDuplicate(nums) {
let duplicates = new Set();
for (let num of nums) {
if (hashSet.has(num))
return true;
hashSet.add(num);
}
return false;
}
.includes()
方法function containsDuplicate(nums) {
let duplicates = [];
for (let num of nums) {
if (duplicates.includes(num))
return true;
hashSet.add(num);
}
return false;
}
我只能告诉你 LeetCode 不会接受数组的解决方案。我收到“超过时间限制”错误,并且只有 70/75 的测试用例通过。因此,在非常高的输入下,.includes()
将无法执行。