Lazy Cartesian Product (v4)

Revision 4 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;
    }
      
    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) {
      return {
        set: set,
        pos: null,
        reset: function() { this.pos = null; },
        next: function() {
          var s, p, step;
          if (this.pos == null) {
            this.pos = this.set.map(function() {
              return 0;
            });
            return true;
          }
          for (s = 0; s < this.set.length; s++) {
            p = (this.pos[s] + 1) % this.set[s].length;
            step = p > this.pos[s];
            this.pos[s] = p;
            if (step) return true;
          }
          this.reset();
          return false;
        },
        item: function(p, s) { return this.set[s][p]; },
        "do": function(f) { 
          return f.apply(null, this.pos.map(this.item, this));
        }
      }
    }
    
    function lazyProduct1b(arrays,callback){
      function recurse(arrays,callback,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 ? values.concat(head[i]) : [head[i]];
          if (dive) recurse(rest,callback,moreValues);
          else      callback.apply(this,moreValues);
        }
      }
      recurse(arrays,callback);
    }
    
    function callback(){}

Test runner

Ready to run.

Testing in
TestOps/sec
Phrogz
lazyProduct1($sets,callback);
ready
RobW
lazyProduct2($sets,callback);
ready
Tomalak
var iter = lazyCartesianIterator($sets);
while (iter.next()) iter.do(callback);
ready
Phrogz 2
lazyProduct1b($sets,callback);
ready

Revisions

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