Lazy Cartesian Product (v21)

Revision 21 of this benchmark created on

Setup

$sets = [];
    for (var i=0;i<6;++i){
      var a = $sets[i] = [];
      for (var j=0;j<6;++j) a[j]=j+""+Math.random();
    }
      
    function lazyProduct1(arrays,callback,values){
      if (!values) values=[];
      var head = arrays[0], rest = arrays.slice(1), dive=rest.length>0;
      for (var i=0,len=head.length;i<len;++i){
        var moreValues = values.concat(head[i]);
        if (dive) lazyProduct1(rest,callback,moreValues);
        else      callback.apply(this,moreValues);
      }
    }
    
    function lazyProduct2(sets, holla) {
        var setLength = sets.length;
        function helper(array_current, set_index) {
            if (++set_index >= setLength) {
                holla.apply(null, array_current);
            } else {
                var array_next = sets[set_index];
                for (var i=0; i<array_next.length; i++) {
                    helper(array_current.concat(array_next[i]), set_index);
                }
            }
        }
        helper([], -1);
    }
    
    function LazyCartesianIterator(set) {
      var pos = null, 
          len = set.map(function (s) { return s.length; });
      
      this.next = function () {
        var s, l=set.length, p, step;
        if (pos == null) {
          pos = set.map(function () { return 0; });
          return true;
        }
        for (s=0; s<l; s++) {
          p = (pos[s] + 1) % len[s];
          step = p > pos[s];
          if (s<l) pos[s] = p;
          if (step) return true;
        }
        pos = null;
        return false;
      };
    
      this.do = function (callback) { 
        var s=0, l=set.length, args = [];
        for (s=0; s<l; s++) args.push(set[s][pos[s]]);
        return callback.apply(set, args);
      };
    }
    
    function lazyProduct1b(arrays,callback){
      function recurse(arrays,callback,values){
        var head=arrays[0],len=head.length;
        if (arrays.length==1){    
          for (var i=0,n=values.length;i<len;++i){
            values[n]=head[i];
            callback.apply(this,values);
          }
        }else{
          for (var i=0;i<len;++i){
            recurse(arrays.slice(1),callback,values.concat(head[i]));
          }
        }
      }
      recurse(arrays,callback,[]);
    }
    
    var every = function (arr, fn) {
      if (arr.every) {
        return arr.every(fn);
      }
      var ret;
      for (var i = 0, n = arr.length; i < n; i++) {
        ret = fn(arr[i], i, arr);
        if (!ret) {
          break;
        }
      }
      return ret;
    }
    
    function lazyProductMZ(lists, fn) {
      var args = [], i = 0, n = lists.length;
      every(lists[i], function _(e) {
        args.push(e);
        i++;
        if (i < n) {
          every(lists[i], _);
        } else {
          var ret = fn.apply(null, args);
        }
        args.pop();
        i--;
        return ret == undefined || ret;
      });
    }
    
    function cartesianProduct_helperWithMap(sets,callback){
      var divmod = sets.map(function(s){ return s.length });
      for (var f=1,l,i=divmod.length;i--;f*=l) divmod[i]=[f,l=divmod[i]];
      for (var i=0,len=divmod[0][0]*divmod[0][1];i<len;++i) callback.apply(this,set(i));
      function set(n){
        return sets.map(function(s,i){
          return s[((n/divmod[i][0])<<0) % divmod[i][1]];
        });
      }
    }
    
    function cartesianProduct_explodedWithMap(sets,callback){
      var divmod = sets.map(function(s){ return s.length });
      for (var f=1,l,i=divmod.length;i--;f*=l) divmod[i]=[f,l=divmod[i]];
      for (var n=0,len=divmod[0][0]*divmod[0][1];n<len;++n){
        var params = sets.map(function(s,i){
          return s[((n/divmod[i][0])<<0) % divmod[i][1]];
        });
        callback.apply(this,params);
      } 
    }
    
    function cartesianProduct_helperNoMap(sets,callback){
      var divmod=[],len=sets.length;
      for (var f=1,l,i=len;i--;f*=l){ divmod[i]=[f,l=sets[i].length] }
      for (var i=0;i<f;++i) callback.apply(this,set(i));
      function set(n){
        for (var result=[],i=len;i--;) result[i]=sets[i][((n/divmod[i][0])<<0) % divmod[i][1]];
        return result;
      }
    }
    
    function cartesianProduct_explodedNoMap(sets,callback){
      var divmod=[],len=sets.length;
      for (var f=1,l,i=len;i--;f*=l){ divmod[i]=[f,l=sets[i].length] }
      for (var n=0;n<f;++n){
        for (var params=[],i=len;i--;) params[i]=sets[i][((n/divmod[i][0])<<0) % divmod[i][1]];
        callback.apply(this,params);
      }
    }
    
    function lazyProductMZ2(sets, block, _context) {
      var n = sets.length, carets = [], args = [];
      function init() {
        for (var i = 0; i < n; i++) {
          carets[i] = 0;
          args[i] = sets[i][0];
        }
      }
      function next() {
        if (!args.length) {
          init();
          return true;
        }
        var i = n - 1;
        carets[i]++;
        if (carets[i] < sets[i].length) {
          args[i] = sets[i][carets[i]];
          return true;
        }
        while (carets[i] == sets[i].length) {
          if (i == 0) {
            return false;
          }
          carets[i] = 0;
          args[i] = sets[i][0];
          carets[--i]++;
        }
        args[i] = sets[i][carets[i]];
        return true;
      }
    
      while (next()) {
        block.apply(_context, args);
      }
    }
    
    function CrossProduct(sets) {
       this.sets = sets;
       this.carets = [];
       this.args = [];
    }
    CrossProduct.prototype = {
       init: function () {
         for (var i = 0, n = this.sets.length; i < n; i++) {
           this.carets[i] = 0;
           this.args[i] = this.sets[i][0];
         }
       },
       next: function () {
         if (!this.args.length) {
           this.init();
           return true;
         }
         var i = this.sets.length - 1;
         this.carets[i]++;
         if (this.carets[i] < this.sets[i].length) {
           this.args[i] = this.sets[i][this.carets[i]];
           return true;
         }
         while (this.carets[i] == this.sets[i].length) {
           if (i == 0) {
             return false;
           }
           this.carets[i] = 0;
           this.args[i] = this.sets[i][0];
           this.carets[--i]++;
         }
         this.args[i] = this.sets[i][this.carets[i]];
         return true;
       },
       do: function (block, _context) {
         return block.apply(_context, this.args);
       }
     }
    
    function crossProduct(sets) {
      var n = sets.length, carets = [], args = [];
      function init() {
        for (var i = 0; i < n; i++) {
          carets[i] = 0;
          args[i] = sets[i][0];
        }
      }
      function next() {
        if (!args.length) {
          init();
          return true;
        }
        var i = n - 1;
        carets[i]++;
        if (carets[i] < sets[i].length) {
          args[i] = sets[i][carets[i]];
          return true;
        }
        while (carets[i] == sets[i].length) {
          if (i == 0) {
            return false;
          }
          carets[i] = 0;
          args[i] = sets[i][0];
          carets[--i]++;
        }
        args[i] = sets[i][carets[i]];
        return true;
      }
      return {
        next: next,
        do: function (block, _context) {
          return block.apply(_context, args);
        }
      }
    }
    
    function LazyProduct(sets){
      for (var dm=[],f=1,l,i=sets.length;i--;f*=l){ dm[i]=[f,l=sets[i].length] }
      this.length = f;
      this.item = function(n){
        for (var c=[],i=sets.length;i--;)c[i]=sets[i][(n/dm[i][0]<<0)%dm[i][1]];
        return c;
      };
    };
    
    function callback(){}

Test runner

Ready to run.

Testing in
TestOps/sec
Phrogz
lazyProduct1($sets,callback);
ready
RobW
lazyProduct2($sets,callback);
ready
Tomalak
iter = new LazyCartesianIterator($sets);
while (iter.next()) iter.do(callback);
ready
Phrogz2
lazyProduct1b($sets,callback);
ready
monzee@gmail.com
lazyProductMZ($sets, callback);
/*
lazyProductMZ([[2,3,4,5],['sweet','hot'],['cats','dogs','hogs']],
  function () { console.log.apply(console, arguments) });
/**/
ready
Phrogz:DirectHelperMap
cartesianProduct_helperWithMap($sets,callback);
ready
Phrogz:DirectExplodedMap
cartesianProduct_explodedWithMap($sets,callback);
ready
Phrogz:DirectHelperNoMap
cartesianProduct_helperNoMap($sets,callback);
ready
Phrogz:DirectExplodedNoMap
cartesianProduct_explodedNoMap($sets,callback);
ready
monzee - imperative
lazyProductMZ2($sets, callback);
ready
monzee - imperative, OOP
var cross = new CrossProduct($sets);
while (cross.next()) { cross.do(callback); }
ready
monzee - imperative, pseudo-OO
var cross = crossProduct($sets);
while (cross.next()) { cross.do(callback); }
ready
Phrogz:LazyProduct
var combos = new LazyProduct($sets);
for (var i=combos.length;i--;){
  callback.apply(this,combos.item(i));
}
 
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.