Lazy Cartesian Product (v26)

Revision 26 of this benchmark created by Gavin Kistner 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) {
      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 = 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

Revisions

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