Optimizing array filtering

Question

var list = [
    { mode: 1, type: 'foo', blah: 1 }, 
    { mode: 3, type: 'foo', blah: 1 }, 
    { mode: 3, type: 'foo', blah: 1 },
    { mode: 1, type: 'bar', blah: 1 }, 
    { mode: 2, type: 'bar', blah: 0 },
    { mode: 3, type: 'bar', blah: 1 }
];

var filter = [
    { propertyName: 'mode', value: 1 }, 
    { propertyName: 'type', value: 'foo' },
    { propertyName: 'blah', value: 1 }
];

var i = 0;

var result1 = $.grep(list, function(x){
    i++;
    return x.type === 'foo' && x.mode === 1 && x.blah === 1;
});

console.log(result1, 'iterations:', i); // 6 iterations

var j = 0;

var result2 = list;

$.each(filter, function(k, filter){
    result2 = $.grep(result2, function(listItem) {
        j++;
        return listItem[filter.propertyName] === filter.value;
    });
});

console.log(result2, 'iterations:', j); // 9 iterations

I would like to optimize my filter method that gives result2 above.

As you can see in result1, the same result can be acheived with less iterations. It might not look like much in my example, but have large lists where performance is an issue.

My question: Is there any way to optimize the filtering for result2 so that it works as the result1 filtering?

if you are ready to use eval probably you can create the filter callback dynamically — Arun P Johny
– Arun P Johny, Commented Jul 4, 2013 at 8:30
@ArunPJohny Yes, I know. Forgot to mention that I'm not a big fan of eval(). So I would like to avoid it if possible. Thanks though — Johan
– Johan, Commented Jul 4, 2013 at 8:31
@Johann: Just flag it as off-topic, that should be sufficient. Don't forget to mention CodeReview as correct SE site. — Zeta
– Zeta, Commented Jul 4, 2013 at 8:48

dandavis · Accepted Answer · 2013-07-04 10:04:11Z

3

you can build a matching object first, and re-use it to avoid the loop-de-loop:

var ob={};
filter.map(function(a,b){
  ob[a.propertyName]=a.value;
})

result2 =  $.grep(list, function(x){
   j++;
   return x.type === ob.tpye && x.mode === ob.mode && x.blah === ob.blah;
});


/* which has the console showing (and yes, they are the same two objects in both results): 
[Object] "iterations:" 6 
[Object] "iterations:" 6   */

full: http://jsfiddle.net/SqJ2y/2/

answered Jul 4, 2013 at 10:04

dandavis

16.8k5 gold badges43 silver badges38 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Johan Over a year ago

Thanks, but don't forget that map() is doing internal loops as well. You should add j++; to the map callback, which will result in the same amount of iterations as before.

Bergi Over a year ago

@dandavis: I thought the OP's point was that the propertyNames (type, mode, blah) are not known before?

dandavis Over a year ago

@Johan: yes, but the small loop to build the match object happens very quickly, and saves enough time from the main loop that it more than pays for itself; way better than any sort of nest loop solution. not all iterations are created equal...

dandavis Over a year ago

@Bergi: yeah, but one can adapt the object builder to build ob on-the-fly and still enjoy the non-nested perf of my solution, since it separates out the two expensive operations instead of stacking them.

Bergi · Accepted Answer · 2013-07-04 16:05:29Z

1

My question: Is there any way to optimize the filtering for result2 so that it works as the result1 filtering?

Yes. grep is building a new array for each filter, and it would be better to do that only once. With the native filter and every methods:

var result3 = list.filter(function(listItem) {
    return filter.every(function(test) {
        return listItem[test.propertyName] === test.value;
    });
});

Plain loops would be faster probably. With jQuery's iteration, which doesn't have an every equivalent, you'd use one anyway:

var result3 = $.grep(list, function(listItem) {
    for (var i=0, l=filter.length; i<l; i++)
        if (listItem[filter[i].propertyName] !== filter[i].value)
            return false;
    return true;
});

Of course that would still need to iterate over the filters every time, you don't really get around that (unless you compile a new Function). But you can furhter optimize the filter array by putting those properties that will filter out the most items in the front.

EDIT: Here's an example with a compiled function:

var result4 = list.filter(new Function("listItem",
    "return "+filter.map(function(test) {
         return "listItem."+test.propertyName+"==="+JSON.stringify(test.value);
// make sure that        ^ these are valid      ^  these are primitive
//                         identifiers             value only
    }).join(" && ")+";"
));

Yet its performance needs to be thoroughly tested, as evaling the function body can introduce a huge overhead especially in older JS engines. It might be faster for thousands of filtered rows though.

edited Jul 4, 2013 at 16:05

answered Jul 4, 2013 at 11:43

Bergi

671k162 gold badges1k silver badges1.5k bronze badges

7 Comments

Johan Over a year ago

Thanks for the feedback. Regarding "unless you compile a new Function": Is it worth looking in to for this scenario? Do you have an example?

Bergi Over a year ago

Do you really have so many items in your list that the nested loops don't cope with that? I don't think the function creation will have a huge performance gain. To make an example I'd need to know whether the filter values can be complex objects or only primitive values.

Johan Over a year ago

There are about 100 filter rows with ~10 columns that are filtered at most. IE7 is the only browser that I'm noticing some performance issues. To answer the latter; filter values are only primitive (Number to be precise).

Bergi Over a year ago

100 filtered list items should definitely not be a performance issue, not even in IE7. Are you sure the filtering part is the slow thing? Usually it's the DOM.

Bergi Over a year ago

Not exaclty, eval is broader ("more hacky") than the Function constructor. But both need to call the parser, that's true.

|

pdjota · Accepted Answer · 2013-07-04 16:51:31Z

0

You may combine both previous answers by @dandavis and @Bergi:

var filtered = list.filter(function(item) {
  return filter.every(function(f) {
    return f.value === item[f.propertyName];
  });
});

edited Jul 4, 2013 at 16:51

answered Jul 4, 2013 at 15:38

pdjota

3,2533 gold badges26 silver badges33 bronze badges

2 Comments

Johan Over a year ago

Ok, and how would you make this dynamic?

pdjota Over a year ago

Yeap, sorry, I didn't get that.

Collectives™ on Stack Overflow

Optimizing array filtering

3 Answers 3

4 Comments

7 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

7 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related