Array Intersect (v2)

Revision 2 of this benchmark created on

Preparation HTML

<script src="https://ajax.googleapis.com/ajax/libs/jquery/1/jquery.min.js">
</script>
<div id="log">
</div>

Setup

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) {
      array1.sort();
      array2.sort();
  
      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);
    }
  }

Test runner

Ready to run.

Testing in
TestOps/sec
slow intersect
slowIntersect(a, b);
ready
shift intersect
shiftIntersect(a, b);
ready
pop intersect
popIntersect(a, b);
ready
pop and reverse
popAndReverseIntersect(a, b);
ready

Revisions

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