Array Intersect (v4)

Revision 4 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) {
    var result = [];
    var a = array1.slice(0);
    var b = array2.slice(0);
    a.sort();
    b.sort();
    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 filter = function(A, B) {
    return A.filter(function(x) {
      return B.indexOf(x) >= 0;
    });
  };
  
  var intersection = function(A, B) {
    var C, a, b, i, j;
    C = [];
    a = A.slice();
    b = B.slice();
    a.sort();
    b.sort();
    i = a.length - 1;
    j = b.length - 1;
    while (i >= 0 && j >= 0) {
      if (a[i] > b[j]) {
        a.pop();
        i--;
      } else if (a[i] < b[j]) {
        b.pop();
        j--;
      } else {
        C.push(a.pop());
        b.pop();
        i--;
        j--;
      }
    }
    return C;
  };
  
  
  
  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
filter
filter(a, b);
ready

Revisions

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