45

I want to keep a list of strings that I will only ever check for the presence of, eg:

corporatePlan = [
    'canDeAuthorize',
    'hasGmailSupport',
    'canShareReports',
    'canSummonKraken',
    'etc'
]

So, when the user tries to summon the kraken, I'll do corporatePlan.indexof('canSummonKraken') != -1 to see if he can.

A coworker suggests that it would be faster to store it as an object:

"Corporate Plan" = {
    'canDeAuthorize' : null,
    'hasGmailSupport' : null,
    'canShareReports' : null,
    'canSummonKraken' : null,
    'etc' : null
}

And just do something like 'canSummonKraken' in corporatePlan to check if the plan contains that key. This makes sense in a classic CS sense, since of course 'contains' is constant time on a map and linear on an array. Does this check out against how arrays and objects are implemented under the hood in JS, though?

In our particular case, with less than 100 elements, the speed doesn't matter much. But for a larger array, which way would be faster on access?

3
  • Don't forget the commas after the nulls in your object literal. Oct 12, 2011 at 9:30
  • @Fish: FWIW, I updated my answer to offer a third option which I think would be a fairly normal way to go. Oct 12, 2011 at 10:58
  • 1
    check this benchmark: jsben.ch/#/Y9jDP Oct 24, 2016 at 8:35

5 Answers 5

33

In JavaScript, you're typically dealing with with a wide variety of implementations (unless you're using it in a controlled environment like a server where you choose the engine), and so the answer to specific performance questions tend to be "it depends, check it on the engines you're going to be using." What's fastest on one implementation may be slower on another, etc. http://jsperf.com is handy for this sort of thing.

That said, I would expect in to be a clear winner here. Array#indexOf has to access array indexes in a search, and array indexes are properties just like any other property. So accessing array index 0 to see if it's the desired string requires looking up 0 just like the other requires looking up the property "canSummonKraken" (and then it has to do a string comparison afterward). (Yes, array indexes are properties. Arrays in JavaScript aren't really arrays at all.) And indexOf may have to access several properties during its search, whereas in will only have to access one. But again, you'll need to check it in your target environemnts to be sure, some implementations may optimize arrays that have contiguous index ranges (but the slowest ones definitely don't, and of course if you're worried about speed, you're worried about what's fastest on the slowest engines, like IE's).

Also note that not all JavaScript engines even have Array#indexOf yet. Most do, but there are still some older ones kicking around (I'm looking at you, Microsoft) that don't.

You also have the question of whether to use in or hasOwnProperty. Using in has the advantage that it's an operator, not a function call; using hasOwnProperty has the advantage that it will only look at the specific object instance and not its prototype (and its prototype, etc.). Unless you have a very deeply inherited hierarchy (and you don't in your example), I bet in wins, but it's useful to remember that it does check the hierarchy.

Also, remember that "canSummonKraken" in obj will be true in the example object literal you showed, because the object does have the property, even though the value of the property is null. You have to not have the property at all for in to return false. (Instead of in, you might just use true and false and look it up as obj.canSummonKraken.)

So your options are:

  1. Your array method:

    corporatePlan = [
        'canDeAuthorize',
        'hasGmailSupport',
        'canShareReports',
        'canSummonKraken',
        'etc'
    ];
    
    console.log(corporatePlan.indexOf("canSummonKraken") >= 0);  // true
    console.log(corporatePlan.indexOf("canDismissKraken") >= 0); // false
    

    ...which I wouldn't recommend.

  2. The in method:

    corporatePlan = {
        'canDeAuthorize'  : null,
        'hasGmailSupport' : null,
        'canShareReports' : null,
        'canSummonKraken' : null,
        'etc'             : null
    };
    
    console.log("canSummonKraken" in corporatePlan);  // true
    console.log("canDismissKraken" in corporatePlan); // false
    

    Probably faster than the indexOf, but I'd test it. Useful if the list could be very long and if you're going to have a lot of these objects, because it only requires that the "truthy" properties exist at all. An empty object represents a plan where the user can't do anything, and is quite small.

    I should note two things here:

    1. in checks the prototype of the object as well, so if you had settings like toString or valueOf, you'd get false positives (as those are properties nearly all objects get from Object.prototype). On an ES5-enabled browser, you can avoid that problem by creating your object with a null prototype: var corporatePlan = Object.create(null);

    2. Perhaps because it checks prototypes, the in operator is surprisingly slow on some engines.

    Both of those issues can be solved by using hasOwnProperty instead:

    console.log(corporatePlan.hasOwnProperty("canSummonKraken"));  // true
    console.log(corporatePlan.hasOwnProperty("canDismissKraken")); // false
    

    One would think an operator would be faster than a method call, but it turns out that's not reliably true cross-browser.

  3. The flags method:

    corporatePlan = {
        'canDeAuthorize'   : true,
        'hasGmailSupport'  : true,
        'canShareReports'  : true,
        'canSummonKraken'  : true,
        'canDismissKraken' : false,
        'etc'              : true
    };
    
    console.log(corporatePlan.canSummonKraken);  // "true"
    console.log(corporatePlan.canDismissKraken); // "false"
    
    // or using bracketed notation, in case you need to test this
    // dynamically
    console.log(corporatePlan["canSummonKraken"]);  // "true"
    console.log(corporatePlan["canDismissKraken"]); // "false"
    
    // example dynamic check:
    var item;
    item = "canSummonKraken";
    console.log(corporatePlan[item]);  // "true"
    item = "canDismissKraken";
    console.log(corporatePlan[item]);  // "false"
    

    ...which would be a fairly normal way to go, probably faster than in, and probably at least as fast as hasOwnProperty. (But see my opening paragraph: Test in your environment. :-) )

1
  • +1, I agree, haven't tested it, but in doesn't have to look up items like indexing does.
    – vgru
    Oct 12, 2011 at 9:41
16

I have tested it: http://jsperf.com/array-indexof-vs-object-s-in-operator/4

When finding the first element, both have good results depending on which browser is in use. So finding the last element, the in Operator is much faster.

But then I used a variant with the typeof operator, which is much faster than both:

if (typeof obj['that'] !== "undefined") {
  // found
}
5
  • 8
    Why typeof !== 'undefined', instead of !== undefined? May 6, 2013 at 19:18
  • 1
    typeof returns a string not an object; you're adding an extra coercion there. developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…
    – Nevir
    Aug 18, 2014 at 22:35
  • @Nevir he means obj['that'] !== undefined which is way faster than string comparison. Nov 2, 2014 at 9:31
  • 3
    undefined is not a constant and can be overwritten. It's much more secure to check for "undefined".
    – oncode
    Nov 5, 2014 at 12:37
  • 7
    @oncode This is no longer true in modern browsers; what's more, this was completely paranoid to begin with. typeof code looks more convoluted.
    – AlexG
    Sep 4, 2016 at 8:55
11

Here is a benchmark http://jsperf.com/array-indexof-vs-object-keys. In chrome and in firefox, checking presence of a key in object is 100% faster than scanning the array.

results

But if you take the initialization time into account, the difference cancels out, objects takes way more time to initialize than arrays.

enter image description here

1
  • To test correctly you should "remove" init times: in both cases init two entities -- object and array. And then in 1st case test only array and in 2nd -- object.
    – gaRex
    Mar 13, 2016 at 20:31
0

Object Reference is the clear winner

I ran a much simpler test that only really tests the: array.indexOf operation and compares to the object[key] reference and value here.

test array.indexOf(key) v. object[key]

This shows that the object[key] operator is ~6X faster when just 1 key is involved and the lookup fails.

This is really a worst case lookup (fail) on the best case dataset (1 entry), should serve as a good proxy for most of these types of operations.

The speed gap gets wider with each key added to the source Array a/Object o.

Object reference is the clear winner.

0

i see Boolean(corporatePlan[item]) as a clear

const t0 = performance.now();
const a = [], b=[];
function getRandomInt(max) {
  return Math.floor(Math.random() * Math.floor(max));
}
for(let i=0; i<1000; i++) a.push((i+1)+"");
for(let i=0; i<100; i++) b.push(getRandomInt(10000)+"");
const bmap = a.reduce((map, x)=>{map[x]=1; return map;}, {});
const c = b.filter((x)=>x in bmap);
const t1 = performance.now();
console.log("Call to doSomething took " + (t1 - t0) + " milliseconds.");

// Call to doSomething took 0.360000180080533 milliseconds.
// ---------------------------------------------------------------------------------

const t0 = performance.now();
const a = [], b=[];
function getRandomInt(max) {
  return Math.floor(Math.random() * Math.floor(max));
}
for(let i=0; i<1000; i++) a.push((i+1)+"");
for(let i=0; i<100; i++) b.push(getRandomInt(10000)+"");
const c = b.filter((x)=>a.indexOf(x) !== -1);
const t1 = performance.now();
console.log("Call to doSomething took " + (t1 - t0) + " milliseconds.");

// Call to doSomething took 0.5349998828023672 milliseconds.
// ---------------------------------------------------------------------------------

const t0 = performance.now();
const a = [], b=[];
function getRandomInt(max) {
  return Math.floor(Math.random() * Math.floor(max));
}
for(let i=0; i<1000; i++) a.push((i+1)+"");
for(let i=0; i<100; i++) b.push(getRandomInt(10000)+"");
const bmap = a.reduce((map, x)=>{map[x]=1; return map;}, {});
const c = b.filter((x)=>typeof(bmap[x]) !== "undefined");
const t1 = performance.now();
console.log("Call to doSomething took " + (t1 - t0) + " milliseconds.");

// Call to doSomething took 0.3500001039355993 milliseconds.
// ---------------------------------------------------------------------------------



const t0 = performance.now();
const a = [], b=[];
function getRandomInt(max) {
  return Math.floor(Math.random() * Math.floor(max));
}
for(let i=0; i<1000; i++) a.push((i+1)+"");
for(let i=0; i<100; i++) b.push(getRandomInt(10000)+"");
const bmap = a.reduce((map, x)=>{map[x]=1; return map;}, {});
const c = b.filter((x)=>Boolean(bmap[x]));
const t1 = performance.now();
console.log("Call to doSomething took " + (t1 - t0) + " milliseconds.");

// Call to doSomething took 0.260000117123127 milliseconds.
// ---------------------------------------------------------------------------------

const t0 = performance.now();
const a = [], b=[];
function getRandomInt(max) {
  return Math.floor(Math.random() * Math.floor(max));
}
for(let i=0; i<1000; i++) a.push((i+1)+"");
for(let i=0; i<100; i++) b.push(getRandomInt(10000)+"");
const bmap = a.reduce((map, x)=>{map[x]=1; return map;}, {});
const c = b.filter((x)=>bmap[x]);
const t1 = performance.now();
console.log("Call to doSomething took " + (t1 - t0) + " milliseconds.");

// Call to doSomething took 0.3450000658631325 milliseconds.
// ---------------------------------------------------------------------------------

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.