Array intersections

JavaScript performance comparison

Test case created by Krinkle and last updated

Preparation code

 
<script>
Benchmark.prototype.setup = function() {
    // Each sample data has only numbers, and no duplicates
    // Order is not to be relied on.
    var foo = [495, 490, 485, 480, 475, 470, 465, 460, 455, 450, 445, 440, 435, 430, 425, 420, 415, 410, 405, 400, 395, 390, 385, 380, 375, 370, 365, 360, 355, 350, 345, 340, 335, 330, 325, 320, 315, 310, 305, 300, 295, 290, 285, 280, 275, 270, 265, 260, 255, 250, 245, 240, 235, 230, 225, 220, 215, 210, 205, 200, 195, 190, 185, 180, 175, 170, 165, 160, 155, 150, 145, 140, 135, 130, 125, 120, 115, 110, 105, 100, 95, 90, 85, 80, 75, 70, 65, 60, 55, 50, 45, 40, 35, 30, 25, 20, 15, 10, 5, 0],
        bar = [0, 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98, 105, 112, 119, 126, 133, 140, 147, 154, 161, 168, 175, 182, 189, 196, 203, 210, 217, 224, 231, 238, 245, 252, 259, 266, 273, 280, 287, 294, 301, 308, 315, 322, 329, 336, 343, 350, 357, 364, 371, 378, 385, 392, 399, 406, 413, 420, 427, 434, 441, 448, 455, 462, 469, 476, 483, 490, 497, 504, 511, 518, 525, 532, 539, 546, 553, 560, 567, 574, 581, 588, 595, 602, 609, 616, 623, 630, 637, 644, 651, 658, 665, 672, 679, 686, 693];
   
   
    // Base
   
    function test_indexOf(a, b) {
      var i, len, c = [];
      for (i = 0, len = a.length; i < len; i++) {
        if (b.indexOf(a[i]) !== -1) {
          c.push(a[i]);
        }
      }
      return c;
    }
   
    // @Christian
   
    function test_forFor(a, b) {
      var i, j, ilen, jlen, c = [];
      for (i = 0, ilen = a.length; i < ilen; i++) {
        for (j = 0, jlen = b.length; j < jlen; j++) {
          if (a[i] === b[j]) {
            c.push(a[i]);
            break;
          }
        }
      }
      return c;
    }
   
    // @Trevor
   
    function test_sortSortWhile(a, b) {
      function numerically(a, b) {
        return a - b;
      }
      a = a.sort(numerically);
      b = b.sort(numerically);
      var common = [];
      ai = 0;
      bi = 0;
      alen = a.length;
      blen = b.length;
      while (ai < alen && bi < blen) {
        if (a[ai] < b[bi]) {
          ai++;
        } else if (a[ai] == b[bi]) {
          common[common.length] = a[ai];
          ai++;
          bi++;
        } else {
          bi++;
        }
      }
      return common;
    }
   
    // @Trevor
   
    function test_objectKeys(a, b) {
      var keys, i, len, common;
      keys = {};
      for (i = 0, len = a.length; i < len; i++) {
        keys[a[i]] = true;
      }
      common = [];
      for (i = 0, len = b.length; i < len; i++) {
        if (keys[b[i]] !== undefined) {
          common[common.length] = b[i];
        }
      }
      return common;
    }
   
    // @Dan
   
   
    function test_regexp(a, b) {
      var searchIn = ',' + a.join(',,') + ',',
          regex = new RegExp(',(' + b.join('),|,(') + '),', 'g'),
          c = [],
          match = regex.exec(searchIn);
      while (match) {
        c[c.length] = Number(match[0].substring(1, match[0].length - 1));
        match = regex.exec(searchIn);
      }
      return c;
    }
   
    // @Rob Moen
   
   
    function test_objectKeys2(a, b) {
      var i, c = [].concat(a).concat(b),
          cLen = c.length,
          index = {},
          res = [],
          key;
   
      for (i = 0; i < cLen; i++) {
        if (index[c[i]]) {
          res[res.length] = c[i];
        } else {
          index[c[i]] = 1;
        }
      }
   
      return res;
    }
   
    // @Rob Moen
   
   
    function test_objectKeys3(a, b) {
      var i, c = a.slice().concat(b),
          cLen = c.length,
          index = {},
          res = [],
          key;
   
      for (i = 0; i < cLen; i++) {
        if (index[c[i]]) {
          res[res.length] = c[i];
        } else {
          index[c[i]] = 1;
        }
      }
   
      return res;
    }
   
   
    var test_primeIntersection = (function() {
      var primes = [2];
      var factors = [];
   
      function getPrime(n) {
        var candidate = primes[primes.length - 1];
        if (primes[n] !== undefined) {
          return primes[n];
        } else {
          while (primes.length - 1 < n) {
            candidate += 1;
            if (isPrime(candidate)) {
              primes.push(candidate);
            }
          }
          return candidate;
        }
      }
   
      function isPrime(candidate) {
        var i, len = primes.length;
        for (i = 0; i < len; i++) {
          if (candidate % primes[i] === 0) {
            return false;
          }
        }
        return true;
      }
   
      function isInFactorization(num) {
        for (i = 0; i < factors.length; i++) {
          if (factors[i] % num === 0) {
            return true;
          }
        }
        return false;
      }
   
      // @marktraceur
   
   
      function getIntersection(one, two) {
        var i, thisPrime, common = [],
            oneResult = 1;
        for (i = 0; i < one.length; i++) {
          thisPrime = getPrime(one[i]);
          if (oneResult * thisPrime > 14119963421434) {
   
            factors.push(oneResult);
            oneResult = 1;
          }
          oneResult *= thisPrime;
        }
        factors.push(oneResult);
   
        for (i = 0; i < two.length; i++) {
          if (isInFactorization(getPrime(two[i]))) {
            common.push(two[i]);
          }
        }
   
        return common;
      }
   
      return getIntersection;
   
    })();
};
</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
indexOf
test_indexOf(foo, bar);
pending…
forFor
test_forFor(foo, bar);
pending…
sortSortWhile
test_sortSortWhile(foo, bar);
pending…
objectKeys
test_objectKeys(foo, bar);
pending…
regexp
test_regexp(foo, bar);
pending…
objectKeys
test_objectKeys2(foo, bar);
pending…
objectKey3
test_objectKeys3(foo, bar);
pending…
primeIntersection
test_primeIntersection(foo, bar);
pending…

You can edit these tests or add even more tests to this page by appending /edit to the URL.

Compare results of other browsers

0 comments

Add a comment