Wie kann ich zwei Sätze von 1000 Zahlen miteinander vergleichen?

Question 1

Ich muss ungefähr 1000 Nummern mit 1000 anderen Nummern vergleichen.

Ich habe beide geladen und serverseitig verglichen:

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

Das hat lange gedauert, also habe ich versucht, den gleichen Vergleich clientseitig mit zwei versteckten durchzuführen
div Elemente. Dann verglichen sie mit JavaScript. Es dauert immer noch 45 Sekunden, um die Seite zu laden (unter Verwendung von hidden div Elemente).

Ich brauche nicht die Nummern zu laden, die nicht gleich sind.

Gibt es einen schnelleren Algorithmus? Ich denke daran, sie datenbankseitig zu vergleichen und einfach die Fehlernummern zu laden und dann einen Ajax-Aufruf für die verbleibenden Nicht-Fehlernummern durchzuführen. Aber ist eine MySQL-Datenbank schnell genug?

Question 2

Sortieren Sie zuerst die Listen. Dann können Sie beide Listen von Anfang an durchgehen und dabei vergleichen.

Die Schleife würde in etwa so aussehen:

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++;
}

(Das ist JavaScript; Sie könnten es auch serverseitig machen, aber ich kenne kein PHP.)

Bearbeiten – nur um allen Hashtable-Fans (die ich natürlich respektiere) fair zu sein, es ist ziemlich einfach, das in JavaScript zu tun:

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]);

Oder wenn die Zahlen Gleitkommazahlen sind oder sein könnten:

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]);

Da Zahlen ziemlich billig zu hashen sind (sogar in JavaScript ist die Konvertierung in Strings vor dem Hashen überraschend billig), wäre dies ziemlich schnell.

Question 3

Question 4

In Bezug auf die Datenbank kann dies ein Join von 1000 Zeilen mit weiteren 1000 Zeilen sein. Damit kann jedes moderne Datenbanksystem umgehen.

select x from table1
inner join table2
on table1.x = table2.y

wo table1 und table2 sind die betroffenen Zeilen und könnten dieselbe Tabelle sein.

Question 5

Was Sie haben, sollte nicht so lange dauern – was macht doBla()? Ich vermute, das dauert die Zeit? Der Vergleich von zwei Sätzen von 1000000 Zahlen mit demselben Algorithmus dauert im Handumdrehen.

Das ist urkomisch – die Anzahl der Optimierungstechniken als Antworten – das Problem ist nicht Ihr Algorithmus – was auch immer doBla() tut, nimmt die Zeit um ein Vielfaches länger in Anspruch, als jede Optimierung Ihnen helfen würde 🙂 esp. da die Sets nur 1000 lang sind und man sie erst sortieren muss..

Question 6

Vielleicht schneiden Sie einfach die Array-Werte, um Zahlen zu finden, die in beiden Arrays vorhanden sind?

$result = array_intersect($numbers1, $numbers2);
foreach ($result as $val)
  doBla();

Question 7

Wenn Sie zuerst Liste2 sortieren und dann eine binäre Suche nach jeder Zahl in Liste1 durchführen, werden Sie eine enorme Geschwindigkeitssteigerung feststellen.

Ich bin nicht ein PHP-Typ, aber das sollte Sie auf die Idee bringen:

sort($numbers2);

foreach($numbers1 as $n1)
{
   if (BinarySearch($numbers2, $n1) >= 0) {
     doBla();
 }
}

Da ich kein PHP-Typ bin, kenne ich die Bibliothek nicht, aber ich bin sicher, dass das Sortieren und die binäre Suche einfach genug zu finden sein sollten.

Notiz: Falls Sie mit einer binären Suche nicht vertraut sind; Sie sortieren Liste2, weil binäre Suchen mit sortierten Listen arbeiten müssen.

Question 8

Sortieren Sie sie zuerst.