Lazy Cartesian Product (v27)

Revision 27 of this benchmark created on

Description

See this Stack Overflow question for the requirements and further discussion of the algorithms tested here.

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) lazyProductPhrogz1(rest,callback,moreValues);
        else      callback.apply(this,moreValues);
      }
    }
    
    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 lazyProductPhrogz2(sets,f,context){
      if (!context) context=this;
      var p=[],max=sets.length-1,lens=[];
      for (var i=sets.length;i--;) lens[i]=sets[i].length;
      function dive(d){
        var a=sets[d], len=lens[d];
        if (d==max) for (var i=0;i<len;++i) 
          p[d]=a[i], f.apply(context,p);
        else        for (var i=0;i<len;++i) 
          p[d]=a[i], dive(d+1);
        p.pop();
      }
      dive(0);
    }
    
    function crossProductMonzee(sets, _block, _context) {
      var n = sets.length, carets = [], args = [], lengths = [];
    
      for (var i = 0; i < n; i++) {
        carets[i] = 0;
        args[i] = sets[i][0];
        lengths[i] = sets[i].length;
      }
      carets[n - 1] = -1;
    
      function next() {
        var i = n - 1;
        carets[i]++;
        if (carets[i] < lengths[i]) {
          args[i] = sets[i][carets[i]];
          return true;
        }
        while (carets[i] >= lengths[i]) {
          if (i == 0) {
            return false;
          }
          carets[i] = 0;
          args[i] = sets[i][0];
          carets[--i]++;
        }
        args[i] = sets[i][carets[i]];
        return true;
      }
    
      if (_block) {
        while (next()) _block.apply(_context, args);
        return;
      }
    
      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 = crossProductMonzee($sets);
while (xp.next()) xp.do(callback, this);
ready
Phrogz3
var combos = new LazyProductPhrogz3($sets);
for (var i=combos.length;i--;){
  callback.apply(this,combos.item(i));
}
ready
monzee - alt interface
crossProductMonzee($sets, callback);
ready

Revisions

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