Array Intersect (v3)

Revision 3 of this benchmark created by micha.com 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 && b.length) {
      switch (true) {
        case (a[0] < b[0]):
          a.shift();
          break;
        case (a[0] > b[0]):
          b.shift();
          break;
        default:
          result.push(a.shift());
          b.shift();
          break;
      }
    }
    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) {
      switch (true) {
        case (a[aLast] > b[bLast]):
          a.pop();
          --aLast;
          break;
        case (a[aLast] < b[bLast]):
          b.pop();
          --bLast;
          break;
        default:
          result.push(a.pop());
          b.pop();
          aLast--;
          bLast--;
          break;
      }
    }
    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.