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
Download ZIP

Revisions

  1. @lovasoa lovasoa revised this gist Jan 27, 2014. 1 changed file with 12 additions and 4 deletions.
    16 changes: 12 additions & 4 deletions README.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1,12 +1,20 @@
    <h1>Fastest function to intersect a large number of big arrays in javascript, without dependencies</h1>
    Array intersect
    ===============

    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)
    *

    <h2>Usage</h2>
    Usage
    -----

    <code>array_intersect(array1, array2, ..., arrayN)</code>

    <h2>How it works</h2>
    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.
  2. @lovasoa lovasoa revised this gist Aug 16, 2012. 4 changed files with 109 additions and 94 deletions.
    15 changes: 12 additions & 3 deletions README.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,12 @@
    <h1>Fastest function to intersect two arrays in javascript, without dependencies</h1>
    See benchmarks
    Usage : array_intersect(arr1, arr2)
    <h1>Fastest function to intersect a large number of big arrays in javascript, without dependencies</h1>
    * 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)
    *

    <h2>Usage</h2>
    <code>array_intersect(array1, array2, ..., arrayN)</code>

    <h2>How it works</h2>
    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.
    36 changes: 26 additions & 10 deletions array_intersect.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,16 +1,32 @@
    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;
    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 (var k=shortest.length-1; k>=0; k--) {
    if (obj[shortest[k]]===nOthers) {ret.push(shortest[k]);}

    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;
    }
    1 change: 1 addition & 0 deletions array_intersect.min.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1 @@
    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}
    151 changes: 70 additions & 81 deletions benchmarks.html
    View file
    Original file line number Diff line number Diff line change
    @@ -5,18 +5,34 @@
    <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;
    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 (var k=shortest.length-1; k>=0; k--) {
    if (obj[shortest[k]]===nOthers) {ret.push(shortest[k]);}

    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;
    }
    @@ -80,46 +96,51 @@
    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";
    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);
    }
    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());
    })
    }
    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([1,2,3,4,5],[1,4,3,2,0]);
    array_intersect(smallArrays[0],smallArrays[1]);
    }
    });

    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]);
    array_big_intersect(smallArrays[0],smallArrays[1]);
    }
    });

    JSLitmus.test('2 arrays of 10 numbers : prototype.js', function(count) {
    while (count--) {
    [1,2,3,4,5].intersect([1,4,3,2,0]);
    smallArrays[0].intersect(smallArrays[1]);
    }
    });

    @@ -172,7 +193,6 @@
    }
    });

    bigArrays = arrays.slice(900);
    JSLitmus.test('100 arrays of ~500 numbers : array_intersect', function(count) {
    while (count--) {
    array_intersect.apply(this, bigArrays);
    @@ -194,56 +214,25 @@
    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;
    });
    });

    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('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('2 arrays of 100000 numbers : array_intersect', function(count) {
    while (count--) {
    array_intersect(veryBigArrays[0], veryBigArrays[1]);
    }
    });

    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);
    JSLitmus.test('2 arrays of 100000 numbers : array_big_intersect', function(count) {
    while (count--) {
    array_big_intersect(veryBigArrays[0], veryBigArrays[1]);
    }
    });

    </script>

    </head>
  3. @lovasoa lovasoa revised this gist Aug 16, 2012. 1 changed file with 254 additions and 0 deletions.
    254 changes: 254 additions & 0 deletions benchmarks.html
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,254 @@
    <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>
  4. @lovasoa lovasoa revised this gist Aug 16, 2012. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion README.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,3 @@
    == Fastest function to intersect two arrays in javascript, without dependencies ==
    <h1>Fastest function to intersect two arrays in javascript, without dependencies</h1>
    See benchmarks
    Usage : array_intersect(arr1, arr2)
  5. @lovasoa lovasoa revised this gist Aug 16, 2012. 2 changed files with 17 additions and 8 deletions.
    3 changes: 3 additions & 0 deletions README.md
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,3 @@
    == Fastest function to intersect two arrays in javascript, without dependencies ==
    See benchmarks
    Usage : array_intersect(arr1, arr2)
    22 changes: 14 additions & 8 deletions array_intersect.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,10 +1,16 @@
    function array_intersect() {
    var sorted = Array.prototype.slice.call(arguments).sort(function(i,j){return i.length>j.length;});
    var shortest = sorted[0];
    return shortest.filter(function(elem){
    for (var i=sorted.length-1; i>0; i--){
    if(sorted[i].indexOf(elem)===-1){return false;}
    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;
    }
    }
    return true;
    });
    }
    for (var k=shortest.length-1; k>=0; k--) {
    if (obj[shortest[k]]===nOthers) {ret.push(shortest[k]);}
    }
    return ret;
    }
  6. @lovasoa lovasoa created this gist Aug 15, 2012.
    10 changes: 10 additions & 0 deletions array_intersect.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,10 @@
    function array_intersect() {
    var sorted = Array.prototype.slice.call(arguments).sort(function(i,j){return i.length>j.length;});
    var shortest = sorted[0];
    return shortest.filter(function(elem){
    for (var i=sorted.length-1; i>0; i--){
    if(sorted[i].indexOf(elem)===-1){return false;}
    }
    return true;
    });
    }