Skip to content

Instantly share code, notes, and snippets.

@sehrgut

sehrgut/Javascript Array Intersect README.md

Forked from lovasoa/README.md
Last active June 5, 2021 01:08
Show Gist options
  • Save sehrgut/5991365 to your computer and use it in GitHub Desktop.
Save sehrgut/5991365 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
array_intersect.js
function array_intersect() {
var i, all, shortest, nShortest, n, len, ret = [], obj={}, nOthers;
nOthers = arguments.length-1;
nShortest = arguments[0].length;
shortest = 0;
for (i=0; i<=nOthers; i++){
n = arguments[i].length;
if (n<nShortest) {
shortest = i;
nShortest = n;
}
}
for (i=0; i<=nOthers; i++) {
n = (i===shortest)?0:(i||shortest); //Read the shortest array first. Read the first array instead of the shortest
len = arguments[n].length;
for (var j=0; j<len; j++) {
var elem = arguments[n][j];
if(obj[elem] === i-1) {
if(i === nOthers) {
ret.push(elem);
obj[elem]=0;
} else {
obj[elem]=i;
}
}else if (i===0) {
obj[elem]=0;
}
}
}
return ret;
}
Raw
array_intersect.min.js
function array_intersect(){var a,b,c,d,e,f,g=[],h={},i;i=arguments.length-1;d=arguments[0].length;c=0;for(a=0;a<=i;a++){e=arguments[a].length;if(e<d){c=a;d=e}}for(a=0;a<=i;a++){e=a===c?0:a||c;f=arguments[e].length;for(var j=0;j<f;j++){var k=arguments[e][j];if(h[k]===a-1){if(a===i){g.push(k);h[k]=0}else{h[k]=a}}else if(a===0){h[k]=0}}}return g}
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 i, all, shortest, nShortest, n, len, ret = [], obj={}, nOthers;
nOthers = arguments.length-1;
nShortest = arguments[0].length;
shortest = 0;
for (i=0; i<=nOthers; i++){
n = arguments[i].length;
if (n<nShortest) {
shortest = i;
nShortest = n;
}
}
for (i=0; i<=nOthers; i++) {
n = (i===shortest)?0:(i||shortest); //Read the shortest array first. Read the first array instead of the shortest
len = arguments[n].length;
for (var j=0; j<len; j++) {
var elem = arguments[n][j];
if(obj[elem] === i-1) {
if(i === nOthers) {
ret.push(elem);
obj[elem]=0;
} else {
obj[elem]=i;
}
}else if (i===0) {
obj[elem]=0;
}
}
}
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;
}
setTimeout(function(){
arrays = new Array();
strings = new Array();
var alph = "azertyuiopsdfghjklmwxcvbn,;:1234567890°³µ1";
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 = parseInt(42*Math.random());
arrays[i][j]=rnd;
var str="";
for (var k=0;k<Math.random();k+=0.05) {
str += alph[rnd%42]+"zizi";
}
strings[i].push(str);
}
}
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());
})
}
bigArrays = arrays.slice(900);
}, 10);
JSLitmus.test('2 arrays of 10 numbers : array_intersect', function(count) {
while (count--) {
array_intersect(smallArrays[0],smallArrays[1]);
}
});
JSLitmus.test('2 arrays of 10 numbers : array_big_intersect', function(count) {
while (count--) {
array_big_intersect(smallArrays[0],smallArrays[1]);
}
});
JSLitmus.test('2 arrays of 10 numbers : prototype.js', function(count) {
while (count--) {
smallArrays[0].intersect(smallArrays[1]);
}
});
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]);
}
});
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));
});
setTimeout(function() {
veryBigArrays = [[],[]];
for (var i=0;i<100000;i++){
veryBigArrays[0].push(parseInt(1000*Math.random()));
veryBigArrays[1].push(parseInt(1000*Math.random()))
}
}, 10);
JSLitmus.test('2 arrays of 100000 numbers : array_intersect', function(count) {
while (count--) {
array_intersect(veryBigArrays[0], veryBigArrays[1]);
}
});
JSLitmus.test('2 arrays of 100000 numbers : array_big_intersect', function(count) {
while (count--) {
array_big_intersect(veryBigArrays[0], veryBigArrays[1]);
}
});
</script>
</head>
<body>
</body>
</html>
Raw
Javascript Array Intersect README.md

Fastest function to intersect a large number of big arrays in javascript, without dependencies

* The compressed version is only 345 caracters long. * Faster than common libraries, even a large number of arrays, or on very big arrays. (See benchmarks) *

Usage

array_intersect(array1, array2, ..., arrayN)

How it works

The idea is simple and comes from here: http://pioupioum.fr/developpement/javascript-array-intersection.html.

To make short story even shorter: It creates a javascript object, the keys of which are the elements of the smallest of the arrays we want to intersect.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment