Incorporating the ideas from stereofrog and Christoph and assuming a couple of non-standard iteration methods on arrays and objects/hashes (each
and friends), we can get set difference, union and intersection in linear time in about 20 lines total:
var setOPs = {
minusAB : function (a, b) {
var h = {};
b.each(function (v) { h[v] = true; });
return a.filter(function (v) { return !h.hasOwnProperty(v); });
},
unionAB : function (a, b) {
var h = {}, f = function (v) { h[v] = true; };
a.each(f);
b.each(f);
return myUtils.keys(h);
},
intersectAB : function (a, b) {
var h = {};
a.each(function (v) { h[v] = 1; });
b.each(function (v) { h[v] = (h[v] || 0) + 1; });
var fnSel = function (v, count) { return count > 1; };
var fnVal = function (v, c) { return v; };
return myUtils.select(h, fnSel, fnVal);
}
};
This assumes that each
and filter
are defined for arrays, and that we have two utility methods:
myUtils.keys(hash)
: returns an
array with the keys of the hash
myUtils.select(hash, fnSelector,
fnEvaluator)
: returns an array with
the results of calling fnEvaluator
on the key/value pairs for which
fnSelector
returns true.
The select()
is loosely inspired by Common Lisp, and is merely filter()
and map()
rolled into one. (It would be better to have them defined on Object.prototype
, but doing so wrecks havoc with jQuery, so I settled for static utility methods.)
Performance: Testing with
var a = [], b = [];
for (var i = 100000; i--; ) {
if (i % 2 !== 0) a.push(i);
if (i % 3 !== 0) b.push(i);
}
gives two sets with 50,000 and 66,666 elements. With these values A-B takes about 75ms, while union and intersection are about 150ms each. (Mac Safari 4.0, using Javascript Date for timing.)
I think that's decent payoff for 20 lines of code.