Array Intersect (v5)

Revision 5 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 intersectSafe = function ( a, b ) {
    var ai = 0,
      bi = 0,
      result = [];
    while ( ai < a.length && bi < b.length ) {
      if ( a[ ai ] < b[ bi ] ) {
        ai++;
      } else if ( a[ ai ] > b[ bi ] ) {
        bi++;
      } else /* they're equal */ {
        result.push( a[ai] );
        ai++;
        bi++;
      }
    }
    return result;
  };
  
  var simpleJsLoops = function (x, y){
      var ret = [];
      for (var i = 0; i < x.length; i++) {
          for (var z = 0; z < y.length; z++) {
              if (x[i] == y[z]) {
                  ret.push(x[i]);
                  break;
              }
          }
      }
      return ret;            
  }
  
  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
intersectSafe
intersectSafe(a,b);
ready
simpleJsLoop
simpleJsLoops(a,b)
ready

Revisions

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