LazyCartesianIterator

JavaScript performance comparison

Revision 2 of this test case created by Tomalak

Info

An iterator object that lazily calculates the Cartesian product of a set of arrays.

Preparation code

 
<script>
Benchmark.prototype.setup = function() {
    function callback() { };
   
    var 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 lazyCartesianIterator_0(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 LazyCartesianIterator_1(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 LazyCartesianIterator_2(set) {
      var pos = null, l = set.length,
          len = set.map(function (s) { return s.length; });
   
      this.next = function () {
        var s, 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.item = function(p, s) {
        return set[s][p];
      };
   
      this.do = function (callback) {
        return callback.apply(set, pos.map(this.item));
      };
    }
   
    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);
        }
      }
    }
};
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
1 Initial Version
var iter = lazyCartesianIterator_0(sets);
while (iter.next()) iter.do(callback);
pending…
2 Proper Object
var iter = new LazyCartesianIterator_1(sets);
while (iter.next()) iter.do(callback);
pending…
3 Array.map callback args
var iter = new LazyCartesianIterator_2(sets);
while (iter.next()) iter.do(callback);
pending…
monzee
var xp = crossProduct(sets);
while (xp.next()) xp.do(callback);
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

0 comments

Add a comment