How can I compare two sets of 1000 numbers against each other?

Question

I must check approximately 1000 numbers against 1000 other numbers.

I loaded both and compared them server-side:

foreach( $numbers1 as $n1 ) {   foreach( $numbers2 as $n2 ) {     if( $n1 == $n2 ) {       doBla();     }   } } 

This took a long time, so I tried to do the same comparison client side using two hidden div elements. Then compared them using JavaScript. It still takes 45 seconds to load the page (using hidden div elements).

I do not need to load the numbers that are not the same.

Is there a faster algorithm? I am thinking of comparing them database side and just load the error numbers, then do an Ajax call for the remaining non-error numbers. But is a MySQL database fast enough?

Answer 1

Sort the lists first. Then you can walk up both lists from the start, comparing as you go.

The loop would look something like this:

var A = getFirstArray().sort(), B = getSecondArray().sort();  var i = 0, j = 0; while (i < A.length && j < B.length) {     if (A[i] === B[j]) {         doBla(A[i]);         i++; j++;     }     else if (A[i] < B[j]) {         i++;     }     else         j++; } 

(That's JavaScript; you could do it server-side too, but I don't know PHP.)

Edit — just to be fair to all the hashtable fans (whom I respect of course), it's pretty easy to do that in JavaScript:

var map = {}; for (var i = 0; i < B.length; ++i) map[B[i]] = true; // Assume integers. for (var i = 0; i < A.length; ++i) if (map[A[i]]) doBla(A[i]); 

Or if the numbers are or might be floats:

var map = {}; for (var i = 0; i < B.length; ++i) map['' + B[i]] = true; // Assume integers. for (var i = 0; i < A.length; ++i) if (map['' + A[i]]) doBla(A[i]); 

Since numbers are pretty cheap to hash (even in JavaScript, converting to string before hashing is surprisingly cheap), this would be pretty fast.