Skip to content

Instantly share code, notes, and snippets.

@magicento

magicento/README.md

Forked from lovasoa/README.md
Last active August 29, 2015 14:23
Show Gist options
  • Save magicento/2e7b7884e2f5eade13e2 to your computer and use it in GitHub Desktop.
Save magicento/2e7b7884e2f5eade13e2 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
README.md

Fastest function to intersect two arrays in javascript, without dependencies

See benchmarks Usage : array_intersect(arr1, arr2)
Raw
array_intersect.js
function array_intersect() {
var sorted, shortest, ret = [], add, found, obj={}, nOthers;
sorted = Array.prototype.slice.call(arguments).sort(function(i,j){return i.length>j.length;});
nOthers = sorted.length-1;
shortest = sorted[0];
for (var i=nOthers; i>0; --i) {
for (var j=sorted[i].length-1; j>=0; --j) {
obj[sorted[i][j]] = (obj[sorted[i][j]]||0)+1;
}
}
for (var k=shortest.length-1; k>=0; k--) {
if (obj[shortest[k]]===nOthers) {ret.push(shortest[k]);}
}
return ret;
}
Raw
benchmarks.html
<html>
<head>
<title>Array intersection</title>
<script src="http://www.broofa.com/Tools/JSLitmus/JSLitmus.js"></script>
<script src="https://ajax.googleapis.com/ajax/libs/prototype/1.7.1.0/prototype.js"></script>
<script>
function array_intersect() {
var sorted, shortest, ret = [], add, found, obj={}, nOthers;
sorted = Array.prototype.slice.call(arguments).sort(function(i,j){return i.length>j.length;});
nOthers = sorted.length-1;
shortest = sorted[0];
for (var i=nOthers; i>0; --i) {
for (var j=sorted[i].length-1; j>=0; --j) {
obj[sorted[i][j]] = (obj[sorted[i][j]]||0)+1;
}
}
for (var k=shortest.length-1; k>=0; k--) {
if (obj[shortest[k]]===nOthers) {ret.push(shortest[k]);}
}
return ret;
}
function array_big_intersect () {
var args = Array.prototype.slice.call(arguments),
aLower = [],
aStack = [],
count,
i,
nArgs,
nLower,
oRest = {},
oTmp = {},
value,
compareArrayLength = function (a, b) {
return (a.length - b.length);
},
indexes = function (array, oStack) {
var i = 0,
value,
nArr = array.length,
oTmp = {};
for (; nArr > i; ++i) {
value = array[i];
if (!oTmp[value]) {
oStack[value] = 1 + (oStack[value] || 0); // counter
oTmp[value] = true;
}
}
return oStack;
};
args.sort(compareArrayLength);
aLower = args.shift();
nLower = aLower.length;
if (0 === nLower) {
return aStack;
}
nArgs = args.length;
i = nArgs;
while (i--) {
oRest = indexes(args.shift(), oRest);
}
for (i = 0; nLower > i; ++i) {
value = aLower[i];
count = oRest[value];
if (!oTmp[value]) {
if (nArgs === count) {
aStack.push(value);
oTmp[value] = true;
}
}
}
return aStack;
}
var arrays = new Array();
var strings = new Array();
arrays[0] = strings [0] = [1];
for (var i=1; i<=1000; i++) {
arrays[i] = new Array();
strings[i] = new Array();
for (var j=0; j<i/2; j++) {
var rnd = new Date();
arrays[i][j]=rnd;
var str="";
for (var k=0;k<Math.random();k+=0.01) {
str += String.fromCharCode(50+100*(parseInt*Math.random()))+"zizi";
}
strings[i].push(str);
}
}
var smallArrays = [];
for (var i=0; i<8000; i++){
smallArrays[i] = [0,0,0,0,0,0,0,0,0,0].map(function(){
return parseInt(2*Math.random());
})
}
JSLitmus.test('2 arrays of 10 numbers : array_intersect', function(count) {
while (count--) {
array_intersect([1,2,3,4,5],[1,4,3,2,0]);
}
});
JSLitmus.test('2 arrays of 10 numbers : array_big_intersect', function(count) {
while (count--) {
array_big_intersect([1,2,3,4,5],[1,4,3,2,0]);
}
});
JSLitmus.test('2 arrays of 10 numbers : prototype.js', function(count) {
while (count--) {
[1,2,3,4,5].intersect([1,4,3,2,0]);
}
});
JSLitmus.test('8000 arrays of 10 numbers : array_intersect', function(count) {
while (count--) {
array_intersect.apply(this,smallArrays);
}
});
JSLitmus.test('8000 arrays of 10 numbers : array_big_intersect', function(count) {
while (count--) {
array_big_intersect.apply(this,smallArrays);
}
});
JSLitmus.test('2 arrays of 500 numbers : array_intersect', function(count) {
while (count--) {
array_intersect(arrays[999], arrays[1000]);
}
});
JSLitmus.test('2 arrays of 500 numbers : array_big_intersect', function(count) {
while (count--) {
array_big_intersect(arrays[999], arrays[1000]);
}
});
JSLitmus.test('2 arrays of 500 numbers : PROTOTYPE.JS intersect', function(count) {
while (count--) {
arrays[999].intersect(arrays[1000]);
}
});
JSLitmus.test('2 arrays of 500 strings : array_intersect', function(count) {
while (count--) {
array_intersect(strings[999], strings[1000]);
}
});
JSLitmus.test('2 arrays of 500 strings : array_big_intersect', function(count) {
while (count--) {
array_big_intersect(strings[999], strings[1000]);
}
});
JSLitmus.test('2 arrays of 500 strings : PROTOTYPE.JS intersect', function(count) {
while (count--) {
strings[999].intersect(strings[1000]);
}
});
bigArrays = arrays.slice(900);
JSLitmus.test('100 arrays of ~500 numbers : array_intersect', function(count) {
while (count--) {
array_intersect.apply(this, bigArrays);
}
});
JSLitmus.test('100 arrays of ~500 numbers : array_big_intersect', function(count) {
while (count--) {
array_big_intersect.apply(this, bigArrays);
}
});
JSLitmus.test('300 arrays of numbers : array_intersect', function() {
array_intersect.apply(this, arrays.slice(200,300));
});
JSLitmus.test('300 arrays of numbers : array_big_intersect', function() {
array_big_intersect.apply(this, arrays.slice(200,300));
});
var veryBigArrays = [[],[]];
for (var i=0;i<5000;i++){
veryBigArrays[0].push(parseInt(1000*Math.random()));
veryBigArrays[1].push(parseInt(1000*Math.random()))
}
JSLitmus.test('2 arrays of 5000 numbers : array_intersect', function() {
array_intersect(veryBigArrays[0], veryBigArrays[1]);
});
JSLitmus.test('2 arrays of 5000 numbers : array_big_intersect', function() {
array_big_intersect(veryBigArrays[0], veryBigArrays[1]);
});
JSLitmus.test('manual filter', function() {
var tab=[];
for (var i=0;i<veryBigArrays[0].length;i++){
if (veryBigArrays[0][i]>500) tab.push(veryBigArrays[0][i]);
}
return tab;
});
JSLitmus.test('Array.filter', function() {
return veryBigArrays[0].filter(function(e){
return e>500;
});
});
JSLitmus.test('manual reduce', function() {
var res={};
for (var i=0;i<veryBigArrays[0].length;i++){
res[veryBigArrays[0][i]] = 1;
}
return res;
});
JSLitmus.test('Array.reduce', function() {
return veryBigArrays[0].reduce(function(p,c){
p[c] = 1; return p;
}, {});
});
JSLitmus.test('manual search', function() {
for (var i=0;i<veryBigArrays[0].length;i++){
if(veryBigArrays[0][i] === 8) return i;
}
});
JSLitmus.test('Array.indexOf', function() {
return veryBigArrays[0].indexOf(8);
});
</script>
</head>
<body>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment