这个问题在这里已有答案:
我在答案中看到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)吗?
如果有人读过specification的has()
,就会有一个描述它的算法:
Set.prototype.has(value)
的算法:
采取以下步骤:
- 设S为该值。
- 如果Type(S)不是Object,则抛出TypeError异常。
- 如果S没有[[SetData]]内部插槽,则抛出TypeError异常。
- 令条目为List的S [[SetData]]内部插槽的值。
- 对每个作为条目元素的e重复, 如果e不为空且SameValueZero(e,value)为true,则返回true。
- 返回false。
显然,基于该算法和REPEAT
这个词的存在,人们可能会对它有一些混淆是O(1)
(我们可以认为它可能是O(n)
)。但是,在specification上我们可以读到:
必须使用散列表或其他机制来实现集合对象,这些机制平均提供对集合中元素数量的次线性访问时间。
感谢@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;}
最后,我想为我的答案的第一个版本可能造成的混乱道歉。感谢所有让我更好地理解我的错误。
我不认为具有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;
}