Lazy Cartesian Product (v23)

Revision 23 of this benchmark created by Gavin Kistner 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 callback(){}
      
    function LazyCartesianIteratorTomalak(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 lazyProductRobW(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 lazyProductPhrogz1(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) lazyProduct(rest,callback,moreValues);
        else      callback.apply(this,moreValues);
      }
    }
    
    function lazyProductPhrogz2(sets,f){
      function dive(sets,f,a){
        var head=sets[0],len=head.length,i=0;
        if (sets.length==1){    
          for (var n=a.length;i<len;++i) a[n]=head[i], f.apply(this,a);
        } else for (;i<len;++i) dive(sets.slice(1),f,a.concat(head[i]));
      }
      dive(sets,f,[]);
    }
    
    function LazyProductPhrogz3(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 crossProductMonzee(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);
        }
      }
    }

Test runner

Ready to run.

Testing in
TestOps/sec
Phrogz1
lazyProductPhrogz1($sets,callback);
ready
RobW
lazyProductRobW($sets,callback);
ready
Tomalak
iter = new LazyCartesianIteratorTomalak($sets);
while (iter.next()) iter.do(callback);
ready
Phrogz2
lazyProductPhrogz2($sets,callback);
ready
monzee
var xp = crossProduct($sets);
while (xp.next()) xp.do(this, callback);

crossProductMonzee
ready
Phrogz3
var combos = new LazyProductPhrogz3($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.