Lazy Cartesian Product

JavaScript performance comparison

Revision 8 of this test case created

Preparation code

 
<script>
Benchmark.prototype.setup = function() {
    $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,[]);
    }
   
    function callback(){}
};
</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
Phrogz
lazyProduct1($sets,callback);
pending…
RobW
lazyProduct2($sets,callback);
pending…
Tomalak
iter = new LazyCartesianIterator($sets);
while (iter.next()) iter.do(callback);
pending…
Phrogz2
lazyProduct1b($sets,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