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

本文介绍了Set.has（）方法是O（1）还是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）的算法： 采取以下步骤：显然，基于该算法以及单词 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（））; .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: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: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）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！