Array Intersect

JavaScript performance comparison

Test case created by Christian G. Warden and last updated

Preparation code

<script src="https://ajax.googleapis.com/ajax/libs/jquery/1/jquery.min.js">
</script>
<div id="log">
</div>
      
<script>
Benchmark.prototype.setup = function() {
  var assert = function(exp, message) {
      if (!exp) {
        $('#log').append('<div>' + message + '</div>');
        console.log(message);
      }
      };
  
  var contains = function(array, value) {
      for (var i = 0, il = array.length; i < il; ++i) {
        if (array[i] === value) {
          return true;
        }
      }
  
      return false;
      };
  
  var slowIntersect = function(array1, array2) {
      var results = [];
      for (var i = 0, il = array1.length; i < il; ++i) {
        if (contains(array2, array1[i])) {
          results.push(array1[i]);
        }
      }
      return results;
      };
  
  var shiftIntersect = function(array1, array2) {
      var result = [];
      var a = array1.slice(0);
      var b = array2.slice(0);
      while (a.length > 0 && b.length > 0) {
        if (a[0] < b[0]) {
          a.shift();
        } else if (a[0] > b[0]) {
          b.shift();
        } else /* they're equal */
        {
          result.push(a.shift());
          b.shift();
        }
      }
      return result;
      };
  
  var popIntersect = function(array1, array2) {
      var result = [];
      var a = array1.slice(0);
      var b = array2.slice(0);
      var aLast = a.length - 1;
      var bLast = b.length - 1;
      while (aLast >= 0 && bLast >= 0) {
        if (a[aLast] > b[bLast]) {
          a.pop();
          aLast--;
        } else if (a[aLast] < b[bLast]) {
          b.pop();
          bLast--;
        } else /* they're equal */
        {
          result.push(a.pop());
          b.pop();
          aLast--;
          bLast--;
        }
      }
      return result;
      };
  
  // keep intersection sorted
  var popAndReverseIntersect = function(array1, array2) {
      var intersect = popIntersect(array1, array2);
      intersect.reverse();
      return intersect;
      };
  
  var x = [1, 2, 3, 4, 5];
  var y = [1, 3, 5];
  var z = [5, 4, 3, 2, 1];
  
  assert(3 == slowIntersect(x, y).length, 'slowIntersect wrong on sorted');
  assert(3 == shiftIntersect(x, y).length, 'shiftIntersect wrong on sorted');
  assert(3 == popIntersect(x, y).length, 'popIntersect wrong on sorted');
  
  /*
  assert(3 == slowIntersect(z,y).length, 'slowIntersect wrong on unsorted');
  assert(3 == shiftIntersect(z,y).length, 'shiftIntersect wrong on unsorted');
  assert(3 == popIntersect(z,y).length, 'popIntersect wrong on unsorted');
  */
  
  var a = [];
  var b = [];
  var i;
  
  for (i = 0; i <= 20000; i++) {
    if (i % 2 == 0) {
      a.push(i);
    }
    if (i % 3 == 0) {
      b.push(i);
    }
  }

};
</script>

Preparation code output

<div id="log"> </div>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in CCBot 2.0.0 / Other 0.0.0
Test Ops/sec
slow intersect
slowIntersect(a, b);
pending…
shift intersect
shiftIntersect(a, b);
pending…
pop intersect
popIntersect(a, b);
pending…
pop and reverse
popAndReverseIntersect(a, b);
pending…

Compare results of other browsers

Revisions

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

0 Comments