Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 971
baklap Avatar asked Oct 15 '10 13:10

baklap


People also ask

How do you compare sets of numbers?

Rules for Comparison of Numbers: Rule I: We know that a number with more digits is always greater than the number with less number of digits. Rule II: When the two numbers have the same number of digits, we start comparing the digits from left most place until we come across unequal digits.

How can you compare numbers against each other to see which one is larger?

When comparing the values of two numbers, you can use a number line to determine which number is greater. The number on the right is always greater than the number on the left. In the example below, you can see that 14 is greater than 8 because 14 is to the right of 8 on the number line.


1 Answers

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.

like image 152
Pointy Avatar answered Oct 07 '22 11:10

Pointy