Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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' : 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?

like image 380
Fishtoaster Avatar asked Oct 12 '11 09:10

Fishtoaster


1 Answers

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

like image 186
T.J. Crowder Avatar answered Sep 20 '22 16:09

T.J. Crowder