Set.has（）方法是O（1）和Array.indexOf O（n）吗？

Question

我在一个答案中看到该Set.has()方法是O（1）和Array.indexOf()O（n）。

var a = [1, 2, 3, 4, 5];
a.indexOf(5);          


s = new Set(a);
s.has(5);              //Is this O(1)?

Set.has()真的是O（1）吗？

Answer 1

我认为具有 5 个元素的数组不是检查时间复杂度的好例子。

因此，基于@Shidersz 的代码段，我创建了一个包含许多元素并调用一次的新代码。

Set.has() 真的是 O(1) 吗？

是的。根据下面的测试结果，Set.has() 的时间复杂度为 O(1)。

const MAX = 10000000
let a = []
a.length = MAX

for (let i = 0; i < MAX; i++) {
  a[i] = i
}

let s = new Set(a)

let o = a.reduce((acc, e) => {
  acc[e] = e
  return acc
}, {})

console.time("Test_Array.IndexOf(0)\t")
a.indexOf(0);
console.timeEnd("Test_Array.IndexOf(0)\t")
console.time("Test_Array.IndexOf(n/2)\t")
a.indexOf(MAX / 2);
console.timeEnd("Test_Array.IndexOf(n/2)\t")
console.time("Test_Array.IndexOf(n)\t")
a.indexOf(MAX);
console.timeEnd("Test_Array.IndexOf(n)\t")

console.time("Test_Set.Has(0)\t\t")
s.has(0)
console.timeEnd("Test_Set.Has(0)\t\t")
console.time("Test_Set.Has(n/2)\t")
s.has(MAX / 2)
console.timeEnd("Test_Set.Has(n/2)\t")
console.time("Test_Set.Has(n)\t\t")
s.has(MAX)
console.timeEnd("Test_Set.Has(n)\t\t")

console.time("Test_Object[0]\t\t")
o[0]
console.timeEnd("Test_Object[0]\t\t")
console.time("Test_Object[n/2]\t")
o[MAX / 2]
console.timeEnd("Test_Object[n/2]\t")
console.time("Test_Object[n]\t\t")
o[MAX]
console.timeEnd("Test_Object[n]\t\t")

.as-console {
  background-color: black !important;
  color: lime;
}

.as-console-wrapper {
  max-height: 100% !important;
  top: 0;
}

Answer 2

如果一个读规范的has()，有描述它的算法：

算法Set.prototype.has(value)：

采取以下步骤：

• 令 S 为 this 值。
• 如果 Type(S) 不是 Object，则抛出 TypeError 异常。
• 如果 S 没有 [[SetData]] 内部槽，则抛出 TypeError 异常。
• 令条目成为 S 的 [[SetData]] 内部槽的值的列表。
• 对作为条目元素的每个 e 重复，
  • 如果 e 不为空且 SameValueZero(e, value) 为真，则返回真。
• 返回假。

显然，基于该算法和单词REPEATone的存在，可能会对其存在一些混淆O(1)（我们可以认为它可能是O(n)）。但是，在规范上我们可以读到：

Set 对象必须使用哈希表或其他机制来实现，这些机制平均提供与集合中元素数量次线性的访问时间。

感谢@CertainPerformance指出这一点。

因此，我们可以创建一个测试来进行比较Array.indexOf()，Set.has()在最坏的情况下，即查找根本不在数组中的项目（感谢@aquinas指出此测试）：

// Initialize array.
let a = [];

for (let i = 1; i < 500; i++)
{
    a.push(i);
}

// Initialize set.
let s = new Set(a);

// Initialize object.
let o = {};
a.forEach(x => o[x] = true);

// Test Array.indexOf().
console.time("Test_Array.indexOf()");
for (let i = 0; i <= 10000000; i++)
{
    a.indexOf(1000);
}
console.timeEnd("Test_Array.indexOf()");

// Test Set.has().
console.time("Test_Set.has()");
for (let i = 0; i <= 10000000; i++)
{
    s.has(1000);
}
console.timeEnd("Test_Set.has()");

// Test Object.hasOwnProperty().
console.time("Test_Object.hasOwnProperty()");
for (let i = 0; i <= 10000000; i++)
{
    o.hasOwnProperty(1000);
}
console.timeEnd("Test_Object.hasOwnProperty()");

.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

现在我们可以看到它的Set.has()性能比Array.indexOf(). 还有一个额外的比较Object.hasOwnProperty()可以作为参考。

结论：

虽然O(1)不能保证复杂性，但规范要求方法在次线性时间内运行。并且Set.has()，通常会比 表现得更好Array.indexOf()。

另一个测试：

在下一个示例中，我们将生成一组随机的样本数据，稍后使用它来比较不同的方法。

// Generate a sample array of random items.

const getRandom = (min, max) =>
{
    return Math.floor(Math.random() * (max - min) + min);
}

let sample = Array.from({length: 10000000}, () => getRandom(0, 1000));

// Initialize array, set and object.

let a = [];

for (let i = 1; i <= 500; i++)
{
    a.push(i);
}

let s = new Set(a);
let o = {};
a.forEach(x => o[x] = true);

// Test Array.indexOf().

console.time("Test_Array.indexOf()");
for (let i = 0; i < sample.length; i++)
{
    a.indexOf(sample[i]);
}
console.timeEnd("Test_Array.indexOf()");

// Test Set.has().
console.time("Test_Set.has()");
for (let i = 0; i < sample.length; i++)
{
    s.has(sample[i]);
}
console.timeEnd("Test_Set.has()");

// Test Object.hasOwnProperty().
console.time("Test_Object.hasOwnProperty()");
for (let i = 0; i < sample.length; i++)
{
    o.hasOwnProperty(sample[i]);
}
console.timeEnd("Test_Object.hasOwnProperty()");

.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

最后，我想为我的答案的第一个版本可能引起的混乱道歉。感谢所有人让我更好地理解我的错误。