CODEWITHSUNDEEP
javascriptjquery
Johan
Johan

Reputation: 35194

Optimizing array filtering

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

Upvotes: 4

Views: 3304

Answers (3)

pdjota
pdjota

Reputation: 3243

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];
  });
});

Upvotes: 0

Bergi
Bergi

Reputation: 664375

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.

Upvotes: 1

dandavis
dandavis

Reputation: 16726

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/

Upvotes: 3

Related Questions