Array Filtering Optimization

Question

http://jsfiddle.net/SqJ2y/

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 filtering method, which gives result2 above.

As you can see in result1 , the same result can be achieved with fewer iterations. In my example, this may not be so much, but you have large lists that have a performance problem.

My question is: is there a way to optimize filtering for result2 so that it works as filtering result1 ?

Answer 1

My question is: is there a way to optimize filtering for result2 so that it works as filtering result1?

Yes. grep creates a new array for each filter, and it would be better to do this only once. Using the native filter and every methods:

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

Simple loops would be faster, perhaps. With a jQuery iteration that does not have the equivalent of every , you will still use:

 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, you still need to iterate over the filter each time, you really won't get around this (unless you compile a new Function ). But you can optimize the filter array by placing these properties, which will filter most of the elements in front.

EDIT: Here is 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(" && ")+";" )); 

However, its performance must be thoroughly tested, since avoiding the function can lead to huge overhead, especially in older JS machines. This can be faster for thousands of filtered rows.

Answer 2

you can first create the corresponding object and reuse it to avoid loop-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/

Answer 3

You can combine both of the previous answers from @dandavis and @Bergi:

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