Search code examples
javascriptalgorithmcode-complexity

Filter once or filter multiple times


I have an array with objects:

objects = [a, b, c, ...]

I have a number of functions which returns true/false for a given object

functions = [f1, f2, f3, ...]

Now I want to get all the objects which passes all functions. What's most efficient?

functions.forEach(function(f) {
       objects = objects.filter(f);
})

OR

objects = objects.filter(function(o) {
       functions.forEach(function(f) {
            if(!f(o)) return false;
       })
})

I'm not sure what's most effecient, it depends on how heavy the filter function is? Are they the same?


Solution

  • I did a little test:

      console.time("Creating objects");
      var objects1 = [];
      var objects2 = [];
      while (objects1.length < 20000) {
        var value = 1000 * Math.random();
        objects1.push({ value: value });
        objects2.push({ value: value });
      }
      console.timeEnd("Creating objects");
    
      console.time("Creating functions")
      var functions = [];
      while (functions.length < 1000) {
        var rnd_value = 1000 * Math.random();
        functions.push(function(o) {
            return o.value >= rnd_value;
        });
      }
      console.timeEnd("Creating functions")
    
      console.time("Functions outer")
    
      functions.forEach(function(f) {
        objects1 = objects1.filter(f);
      });
    
      console.timeEnd("Functions outer");
    
      console.time("Filter outer")
    
      objects2 = objects2.filter(function(o) {
        var ret = true;
        functions.forEach(function(f) {
          if (ret && !f(o)) ret = false;
        });
        return ret;
      });
    
      console.timeEnd("Filter outer");
    

    The result in console was: Functions outer: 3188.918ms Filter outer: 454.249ms

    So I assume the filter function on array is pretty heavy in javascript. In other word, I should call it as few times as possible.