Iterating over JS Object across multiple arrays - Performance

Question

So basically what I'm trying to do here is this:

Lets say you have this object:

{
 owner: 'Richard',
 time: 141381983181,
 type: 'Football',
 approved:['Higgs','Rooney','Jake'],
 pending:['Richmond','Sarah','Evelyin'],
 rejected:['Bilbo','Alice','Marta']
}

Now, what I kinda need is a quick function that would return which 'Name' belongs to what field.

For example: determineUserLevel('Bilbo',aMeeting) //return rejected.

So I wrote one:

function determineUserLevel(spec){

    var event = spec.event,
        user = spec.user;


    if(event.owner === user) return 'owner';

    for(var i = 0 ; i < event.approved.length; i++){

       if(event.approved[i] === user) return 'approved';

    }
    for(var x = 0; x < event.pending.length; x++){

        if(event.pending[x] === user) return 'pending';

    }
    for(var f = 0; f < event.rejected.length; f++){

        if(event.rejected[f] === user) return 'rejected'

    }

    return 'user';

}

Is there any better approach? Performance wise ? maintainable wise? or this is pretty solid?

Thanks.

This question belongs in http://codereview.stackexchange.com/ if it works and you need a better approach. — surajck, Jan 20 '15 at 15:43
It would be helpful if your example of calling the function actually matched the signature of your function. I assume you are actually calling it like this: `determineUserLevel({event:aMeeting, user:"Bilbo"});` — Matt Burland, Jan 20 '15 at 15:46
Unless you list is sorted, a linear search is the best you can do. Unless you transform your arrays into a dictionary / hashset, which maybe useful if they are large and/or you are doing lots of lookups. — Matt Burland, Jan 20 '15 at 15:47
@Linial: I mean sorted, sorted. If it was sorted alphabetically, you could do something like a binary search. But again, unless the list is very long, it's probably not worth the effort. And if the order of the items in the array is actually important, then obviously it's a non-starter. — Matt Burland, Jan 20 '15 at 15:50

Ben McCormick · Answer 1 · 2015-01-20T15:54:13.667

1

Unless your arrays are huge (thousands of items), a function like this will have a negligible performance impact. You should be optimizing for reliability and readability instead.

function determineUserLevel(spec){

    var event = spec.event,
        user = spec.user;


    if(event.owner === user) {
      return 'owner';
    }
    if(event.approved.indexOf(user) > -1) {
      return 'approved';
    }
    if(event.pending.indexOf(user) > -1) {
      return 'pending';
    }
    if(event.rejected.indexOf(user) > -1) {
      return 'rejected';
    }

    return 'user';

}

Using indexOf rather than loops simplifies the code and minimizes the chances of typoing the loop condition. You could also combine the 2 for even more readability.

function determineUserLevel(spec){

    var event = spec.event,
        user = spec.user;


    if(event.owner === user) {
      return 'owner';
    }
    var sets = ['approved','pending','rejected'];

    for(var i=0; i<sets.length; i++) {
       var set = sets[i];
       if(event[set].indexOf(user) > -1) {
         return set
       }
    }

    return 'user';

}

How readable that is is a bit of a judgement call, but it would allow you to scale out to more sets easily without having to repeat yourself.

edited Jan 20 '15 at 15:54

answered Jan 20 '15 at 15:48

Ben McCormick

25,260
12
52
71

This however barely makes a difference. I was hoping for something like parallel search, imagine that a user is rejected, we would have to go across all fields before we realise that, don't you think? I mean , is that even possible? – Linial Jan 20 '15 at 15:50
@Linial: Javascript is single threaded (unless you want to muck about with web workers I guess), but unless you've identified this as an actual bottleneck in your application, I wouldn't bother with it. – Matt Burland Jan 20 '15 at 15:52
Really appreciate your help @MattBurland, hmm I kinda believe this would become a bottle neck in the future though – Linial Jan 20 '15 at 15:55
@Linial how big are your datasets? Unless you are iterating over thousands of items in each list, this is just quite simply not going to be slow. – Ben McCormick Jan 20 '15 at 15:55
Each array would contain 20 strings. In the future though those would become objects, would that impact performance? – Linial Jan 20 '15 at 15:56
@BenMcCormick Haha, I liked that! – Linial Jan 20 '15 at 15:57
@Linial Not in a way you'd notice. You can see here that my way is actually slower, but both of these will run millions of times a second: http://jsperf.com/javascriptisfast – Ben McCormick Jan 20 '15 at 16:02
@BenMcCormick: At least part of your slowness is the extra loop (if you unroll it, like your original suggestion, it's not as bad). The `indexOf` versus iterating with `for` is discussed here: http://stackoverflow.com/questions/6682951/why-is-looping-through-an-array-so-much-faster-than-javascripts-native-indexof – Matt Burland Jan 20 '15 at 16:13
@MattBurland yep, loops are the fastest in general. But I'd stand by my choice of not using them. – Ben McCormick Jan 20 '15 at 16:16
@BenMcCormick: I don't disagree. I think `indexOf` makes the intent much clearer and the code much more concise. It would be even better if we could use [Array.includes](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/includes), but sadly it's not supported by most browsers. – Matt Burland Jan 20 '15 at 16:38

Matt Burland · Answer 2 · 2015-01-20T16:05:13.747

Use an object as a hashset instead of an array of strings. So instead of this:

approved:['Higgs','Rooney','Jake']

change it to this:

approved:{'Higgs':true,'Rooney':true,'Jake':true},

Now lookups are super fast:

if (approved[nameToTest]) {
    return "approved";
}

And obviously the same for all the other array properties.

If you are starting from an array, then transforming it into a hashset is fairly trivial, something like:

approved = ['Higgs', 'Rooney', 'Jake'];

var approvedObj = approved.reduce(function(curr, next) {
  curr[next] = true;
  return curr;
}, {});

alert(JSON.stringify(approvedObj));

Whether the initial cost of the transformation is worth it depends on how big your collection is and how often you need to do a look up.

Collection is about 10,000 "Events || Meetings" , and look-up is about 5,000 times a minute. — Linial, Jan 20 '15 at 16:10

Iterating over JS Object across multiple arrays - Performance

2 Answers2