Performance of array includes vs mapping to an Object and accessing it in JavaScript

Question

According to the fundamentals of CS the search functionality of an unsorted list has to occur in O(n) time where as direct access into an array will occur in O(1) time for HashMaps.

So is it more performant to map an array into a dictionary and then access the element directly or should I just use includes? This question is specifically for JavaScript because I believe this would come down to core implementation details of how includes() and {} is implemented.

let y = [1,2,3,4,5]
y.includes(3)

or...

let y = {
          1: true,
          2: true
          3: true
          4: true
          5: true
        }
5 in y

Answer 1

It's true that object lookup occurs in constant time - O(1) - so using object properties instead of an array is one option, but if you're just trying to check whether a value is included in a collection, it would be more appropriate to use a Set, which is a (generally unordered) collection of values, which can also be looked up in linear time. (Using a plain object instead would require you to have values in addition to your keys, which you don't care about - so, use a Set instead.)

const set = new Set(['foo', 'bar']);
console.log(set.has('foo'));
console.log(set.has('baz'));

This will be useful when you have to look up multiple values for the same Set. But, adding items to the Set (just like adding properties to an object) is O(N), so if you're just going to look up a single value, once, there's no benefit to this nor the object technique, and you may as well just use an array includes test.

Answer 2

Updated 04/29/2020

As the commenter rightly pointed out it would seem V8 was optimizing out the array includes calls. An updated version that assigns to a var and uses it produces more expected results. In that case Object address is fastest, followed by Set has and in a distant third is Array includes (on my system / browser).

All the same, I do stand by my original point, that if making micro-optimizations it is worth testing assumptions. Just make sure your tests are valid ;)

Original

Well. Despite the obvious expectation that Object address and Set has should outperform Array includes, benchmarks against Chrome indicate that implementation trumps expectation.

In the benches I ran against Chrome Array includes was far and away the best performer.

I also tested locally with Node and got more expected results. In that Object address wins, followed closely by Set has, then Array includes was marginally slower than both.

Bottom line is, if you're making micro-optimizations (not recommending that) it's worth benchmarking rather than assuming which might be best for your particular case. Ultimately it comes down to the implementation, as your question implies. So optimizing for the target platform is key.

Here's the results I got:

Node (12.6.0):

ops for Object address 7804199
ops for Array includes 5200197
ops for Set has        7178483

Chrome (75.0):
https://jsbench.me/myjyq4ixs1/1

Answer 3

This isn't necessarily a direct answer to the question but here is a related performance test I ran real quick in my chrome dev tools

function getRandomInt(max) {
    return Math.floor(Math.random() * max);
}
var arr = [1,2,3];
var t = performance.now();
for (var i = 0; i < 100000; i++) {
    var x = arr.includes(getRandomInt(3));
}
console.log(performance.now() - t);
var t = performance.now();
for (var i = 0; i < 100000; i++) {
    var n = getRandomInt(3);
    var x = n == 1 || n == 2 || n == 3;
}
console.log(performance.now() - t);
VM44:9 9.100000001490116
VM44:16 5.699999995529652

I find the array includes syntax nice to look at, so I wanted to know if the performance was likely to be an issue the way I use it, for checking if a variable is one of a set of enums for instance. It doesn't seem to be much of an impact for situations like this with a short list. Then I ran this.

function getRandomInt(max) {
    return Math.floor(Math.random() * max);
}
var t = performance.now();
for (var i = 0; i < 100000; i++) {
    var x = [1,2,3].includes(getRandomInt(3));
}
console.log(performance.now() - t);

var t = performance.now();
for (var i = 0; i < 100000; i++) {
    var n = getRandomInt(3);
    var x = n == 1 || n == 2 || n == 3;
}
console.log(performance.now() - t);
VM83:8 12.600000001490116
VM83:15 4.399999998509884

and so the way I actually use it and like lookin at it is quite worse with performance, despite still not being very significant unless run a few million times, so using it inside of an Array.filter that may run a lot as a react redux selector may not be a great idea like I was about to do when I decided to test this.