Set.has（）方法是O（1）还是Array.indexOf O（n）？ [英] Is the Set.has() method O(1) and Array.indexOf O(n)?
问题描述
我在答案中看到 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）; //这是O（1）吗？
Set.has（）真的是（1）？
如果读过规范 有（），有一个算法描述它：
Set.prototype.has（value）的算法：
采取以下步骤：
- 让S是这个值。
- 如果Type（S）不是Object，则抛出TypeError异常。
- 如果S没有[[SetData] ]]内部插槽，抛出一个TypeError异常。
- 让条目成为S的[[SetData]]内部插槽的值。
- 对每个作为条目元素的e重复，
- 如果e不为空且SameValueZero（e，value）为true，则返回true。
- Retu假的。
显然，基于该算法以及单词<$ c的存在$ c> REPEAT 可能会有一些混淆是 O（1）（我们认为它可能是为O（n））。但是，在规范上，我们可以读取：
必须使用散列表或其他机制来实现集合对象，这些机制平均提供次线性的访问时间集合中元素的数量。
感谢 @CertainPerformance 指出这一点。
因此，我们可以创建一个测试来比较 Array.indexOf（）和 Set.has（） 在最坏的情况下，即查找一个根本不在数组中的项目（感谢 @aquinas 指向此测试）：
//初始化array.let a = []; for（let i = 1; i< 500; i ++）{a。 push（i）;} //初始化set.let s = new Set（a）; //初始化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（令i = 0; i< = 10000000; i ++）{o.hasOwnProperty（1000）;} console.timeEnd（Test_Object.hasOwnProperty（））; < pre class =snippet-code-css lang-css prettyprint-override> .as-console {background-color：black！important; color：lime;}。as-console-wrapper {max-height：100％！important;顶部：0;}
现在我们可以看到 Set.has（）的性能优于 Array.indexOf（）。还有一个额外的比较 Object.hasOwnProperty（）作为参考。
结论：
虽然 O（1）复杂性无法保证，但规范要求方法在次线性时间即可。通常， Set.has（）的性能优于 Array.indexOf（）。
另一个测试：
在下一个例子中，我们将生成一组随机的样本数据，稍后使用它来比较不同的数据方法。
//生成随机items.const getRandom =的示例数组（min，max）=> {return Math.floor（Math.random（）*（max - min）+ min）;} let sample = Array.from（{length：10000000}，（）=> getRandom（ 0,1000））; //初始化数组，set和object.let a = []; for（let i = 1; i< = 500; i ++）{a.push（i）;} let s = new Set （a）;令o = {}; a.forEach（x => o [x] = true）; // Test Array.indexOf（）。console.time（Test_Array.indexOf（））; for（令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;我< sample.length; i ++）{s.has（sample [i]）;} console.timeEnd（Test_Set.has（））; // Test Object.hasOwnProperty（）。console.time（Test_Object.hasOwnProperty（））; for （令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;顶部：0;}
最后我要道歉对于混淆，我的答案的第一个版本可能会导致。感谢所有人让我更好地理解我的错误。
I have seen in an answer that the Set.has() method is O(1) and Array.indexOf() is O(n).
var a = [1, 2, 3, 4, 5];
a.indexOf(5);
s = new Set(a);
s.has(5); //Is this O(1)?
Is Set.has() really O(1) ?
If one read the specification of has(), there is an algorithm describing it:
Algorithm for Set.prototype.has(value):
The following steps are taken:
- Let S be the this value.
- If Type(S) is not Object, throw a TypeError exception.
- If S does not have a [[SetData]] internal slot, throw a TypeError exception.
- Let entries be the List that is the value of S’s [[SetData]] internal slot.
- Repeat for each e that is an element of entries,
- If e is not empty and SameValueZero(e, value) is true, return true.
- Return false.
And apparently, based on that algorithm and the presence of the word REPEAT one can have some confusion about it to be O(1) (we could think it could be O(n)). However, on the specification we can read that:
Set objects must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection.
Thanks to @CertainPerformance for pointing this.
So, we can create a test to compare Array.indexOf() and Set.has() in the worst case, i.e. look for an item that isn't in the array at all (thanks to @aquinas for pointing this test):
// 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;}
And now we can see that Set.has() performs better than Array.indexOf(). There is also an extra comparison to Object.hasOwnProperty() to take as reference.
Conclusion:
While O(1) complexity isn't guaranteed, the specification requires the method to run in sublinear time. And Set.has(), generally, will perform better than Array.indexOf().
Another Test:
On next example, we going to generate a random set of sample data and use it later to compare the differents methods.
// 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;}
Finally I want to apologize for the confusion the first version of my answer could cause. Thanks to all for giving me a better understanding of my mistakes.
这篇关于Set.has（）方法是O（1）还是Array.indexOf O（n）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
