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.
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().
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.
