Lazy Cartesian Product (v32)

Revision 32 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 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

Revisions

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