In JS, which is faster: Object's "in" operator or Array's indexof?

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' : nu开发者_Python百科ll,
    '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?

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

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
}

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.

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

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.

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.

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.
// ---------------------------------------------------------------------------------