Lazy Cartesian Product

JavaScript performance comparison

Revision 26 of this test case created by Gavin Kistner

Info

See this Stack Overflow question for the requirements and further discussion of the algorithms tested here.

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 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);
}
}
}
};
</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
Phrogz1
lazyProductPhrogz1(\$sets,callback);
pending…
RobW
lazyProductRobW(\$sets,callback);
pending…
Tomalak
iter = new LazyCartesianIteratorTomalak(\$sets);
while (iter.next()) iter.do(callback);
pending…
Phrogz2
lazyProductPhrogz2(\$sets,callback);
pending…
monzee
var xp = crossProductMonzee(\$sets);
while (xp.next()) xp.do(callback, this);
pending…
Phrogz3
var combos = new LazyProductPhrogz3(\$sets);
for (var i=combos.length;i--;){
callback.apply(this,combos.item(i));
}
pending…

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

Comment form temporarily disabled.