webentwicklung-frage-antwort-db.com.de

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

Ich muss ungefähr 1000 Zahlen gegen 1000 andere Zahlen prüfen.

Ich habe beide geladen und sie 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 mit zwei versteckten div Elementen durchzuführen. Dann mit JavaScript verglichen. Es dauert immer noch 45 Sekunden, um die Seite zu laden (mit versteckten div-Elementen).

Ich muss nicht die Zahlen laden, die nicht gleich sind.

Gibt es einen schnelleren Algorithmus? Ich denke darüber nach, sie auf der Datenbankseite zu vergleichen und nur die Fehlernummern zu laden. Anschließend werden die restlichen Nichtfehlernummern von Ajax aufgerufen. Aber ist eine MySQL-Datenbank schnell genug?

64
baklap

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

Die Schleife würde ungefähr 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 tun, aber ich kenne PHP nicht.)

Edit - Um allen Hashtable-Fans (die ich natürlich respektiere) fair zu sein, ist es recht einfach, dies 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 Floats 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 für Hashes relativ billig sind (selbst in JavaScript ist das Konvertieren in String vor dem Hashing überraschend günstig), wäre dies ziemlich schnell.

129
Pointy
85
Phill Pafford

In der Datenbank kann dies ein Zusammenfügen von 1000 Zeilen zu weiteren 1000 Zeilen sein. Jedes moderne Datenbanksystem kann damit umgehen.

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

dabei sind table1 und table2 die betroffenen Zeilen und können dieselbe Tabelle sein.

27
Preet Sangha

Was Sie haben sollten, sollte nicht so lange dauern - was tut Bla ()? Ich vermute, dass das Zeit braucht? Der Vergleich von zwei Mengen von 1000000 Zahlen mit demselben Algorithmus nimmt keine Zeit in Anspruch.

Das ist komisch - die Anzahl der Optimierungstechniken als Antwort - das Problem ist nicht Ihr Algorithmus - was auch immer doBla () tut, kostet die Zeit um einen Faktor, der viel größer ist als jede Optimierung, die Ihnen helfen würde :) Da die Sets nur 1000 lang sind, müssen Sie sie zuerst sortieren.

26
markmnl

Vielleicht schneiden Sie einfach die Array-Werte, um in beiden Arrays vorhandene Zahlen zu finden.

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

Wenn Sie list2 zuerst sortieren und dann eine binäre Suche für jede Zahl in list1 durchführen, sehen Sie eine enorme Geschwindigkeitssteigerung.

Ich bin nicht ein PHP Typ, aber das sollte Ihnen die Idee geben:

sort($numbers2);

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

Natürlich bin ich kein PHP - Typ, ich kenne die Bibliothek nicht, aber ich bin sicher, dass Sortieren und binäre Suche leicht zu finden sein sollten.

Hinweis: Falls Sie mit einer binären Suche nicht vertraut sind; Sie sortieren list2, da binäre Suchen mit sortierten Listen durchgeführt werden müssen.

9
Giovanni Galbo

Stop - warum machst du das?

Wenn sich die Nummern bereits in einer SQL-Datenbank befinden, führen Sie einen Join durch und lassen Sie die Datenbank die effizienteste Route ermitteln.

Wenn sie sich nicht in einer Datenbank befinden, wette ich, dass Sie irgendwo von der Spur sind und wirklich darüber nachdenken müssen, wie Sie hierher gekommen sind.

5
dethSwatch

Sortiere sie zuerst.

5
JRL

Ich bin kein PHP - Experte, daher ist möglicherweise ein Debugging erforderlich, aber Sie können dies problemlos in O(n) - Zeit tun:

// Load one array into a hashtable, keyed by the number: O(n).
$keys1 = [];
foreach($numbers1 as $n1) $keys1[$n1] = true;

// Find the intersections with the other array:
foreach($numbers2 as $n2) { // O(n)
  if (isset($keys1[$n2]) { // O(1)
     doBla();
  }
}

Unabhängig davon ist die Kreuzung nicht der Ort, an dem Ihre Zeit vergeht. Selbst eine schlechte Implementierung von O (n ^ 2), wie Sie sie jetzt haben, sollte 1000 Zahlen in einer Sekunde durchlaufen können.

5
munificent
$same_numbers = array_intersect($numbers1, $$numbers2);

foreach($same_numbers as $n)
{
  doBla();
}
4
Cesar

Beide Listen sortieren und dann beide Listen gleichzeitig mit dem sequentiellen Aktualisierungsmuster old-master new-master durchsuchen. Solange Sie die Daten sortieren können, ist dies der schnellste Weg, da Sie wirklich nur einmal die Liste durchlaufen, bis zur größten Länge der größten Liste.

3
skamradt

Ihr Code ist einfach komplizierter als es sein muss.

Angenommen, Sie suchen, dass die Zahlen in jeder Position übereinstimmen (und nicht nur, dass das Array die gleichen Zahlen enthält), Sie können Ihre Schleife auf eine einzige für reduzieren.

<?php
// Fill two arrays with random numbers as proof.
$first_array = array(1000);
$second_array = array(1000);
for($i=0; $i<1000; $i++) $first_array[$i] = Rand(0, 1000);
for($i=0; $i<1000; $i++) $second_array[$i] = Rand(0, 1000);

// The loop you care about.
for($i=0; $i<1000; $i++) if ($first_array[$i] != $second_array[$i]) echo "Error at $i: first_array was {$first_array[$i]}, second was {$second_array[$i]}<br>";

?>

Wenn Sie den obigen Code verwenden, werden Sie nur 1000-mal eine Schleife machen, im Gegensatz zu einer 1000000-maligen Schleife.

Wenn Sie nur prüfen müssen, ob eine Zahl in den Arrays angezeigt wird oder nicht, verwenden Sie array_diff und array_intersect wie folgt:

<?php
// Fill two arrays with random numbers as proof.
$first_array = array(1000);
$second_array = array(1000);
for($i=0; $i<1000; $i++) $first_array[$i] = Rand(0, 1000);
for($i=0; $i<1000; $i++) $second_array[$i] = Rand(0, 1000);

$matches = array_intersect($first_array, $second_array);
$differences = array_diff($first_array, $second_array);

?>
2
Jack Shedd

Sie können dies in der Zeit O(n) tun, wenn Sie die Bucket-Sortierung verwenden. Angenommen, Sie kennen den maximalen Wert, den die Zahlen annehmen können (obwohl es einige Möglichkeiten gibt).

http://en.wikipedia.org/wiki/Bucket_sort

2
ashanan

Vielleicht sehe ich hier nicht etwas, aber es sieht aus wie ein klassischer Fall einer Schnittmenge. Hier sind ein paar Zeilen in Perl, die es tun werden.

foreach $ e (@a, @b) {$ union {$ e} ++ && $ isect {$ e} ++}

@union = Schlüssel% union; @isect = Schlüssel% isect;

Am Ende dieser Codezeile enthält @isect alle Zahlen, die sowohl in @a als auch in @b enthalten sind. Ich bin mir sicher, dass dies mehr oder weniger direkt in PHP übersetzt werden kann. FWIW, das ist mein Lieblingscode aus dem Perl-Kochbuch.

2
Shahbaz

Ich werde eine grafische Benutzeroberfläche in Visual Basic erstellen und prüfen, ob ich die Zahlen nachverfolgen kann

1
edahs

Ein besserer Weg wäre, so etwas zu tun:

// 1. Create a hash map from one of the lists.
var hm = { };
for (var i in list1) {
  if (!hm[list1[i]]) {
    hm[list1[i]] = 1;
  } else { hm[list1[i]] += 1; }
}

// 2. Lookup each element in the other list.
for (var i in list2) {
  if (hm[list2[i]] >= 1) {
    for (var j = 0; j < hm[list2[i]]; ++j) {
      doBla();
    }
  }
}

Dies ist garantiert O(n) [unter der Annahme, dass eine Suche in einer Hash-Map O(1) amortisiert ist.

Update: Der schlimmste Fall dieses Algorithmus wäre O (n2) und es gibt keine Möglichkeit zu reduzieren - es sei denn, Sie ändern die Semantik des Programms. Dies liegt daran, dass das Programm im schlimmsten Fall doBla () n aufruft2 Anzahl, wenn alle Zahlen in beiden Listen gleich sind. Wenn jedoch beide Listen eindeutige Nummern haben (d. H. Im Allgemeinen innerhalb einer Liste eindeutig), dann tendiert die Laufzeit zu O (n).

1
dhruvbird

Ich denke, es wäre viel einfacher, die eingebaute Funktion array_intersect zu verwenden. An Ihrem Beispiel könnten Sie Folgendes tun:

$results = array_intersect($numbers1, $numbers2);
foreach($results as $rk => $rv) {
    doSomething($rv);
}
1
David

Fassen Sie beide Listen zusammen, beginnen Sie am Anfang beider Listen und durchsuchen Sie dann jede Liste gleichzeitig nach ähnlichen Zahlen.

Also, im Pseudocode würde es so etwas wie gehen ...

Mergesort (List A);
Mergesort (list B)

$Apos = 0;
$Bpos = 0;

while( $Apos != A.Length && $Bpos != B.length) // while you have not reached the end of either list
{
if (A[$Apos] == B[$Bpos])// found a match
doSomething();

else if (A[$Apos] > B[$Bpos]) // B is lower than A, so have B try and catch up to A.
$Bpos++;

else if (A[$Apos] < B[$Bpos]) // the value at A is less than the value at B, so increment B
$Apos++;

}

Wenn ich recht habe, ist die Geschwindigkeit dieses Algorithmus O (n logn).

1
waffles

Ich bin nicht sicher, warum Mrk Mnl abgelehnt wurde, aber der Funktionsaufruf ist der Overhead hier. 

Schieben Sie die übereinstimmenden Zahlen in ein anderes Array und doBla () auf nach den Vergleichen. // Testen Sie doBla () und sehen Sie, ob Sie das gleiche Leistungsproblem haben.

1
Martin Blank

Zusammenführen, sortieren und dann zählen

<?php
    $first = array('1001', '1002', '1003', '1004', '1005');
    $second = array('1002', '1003', '1004', '1005', '1006');
    $merged = array_merge($first, $first, $second);
    sort($merged);
    print_r(array_count_values($merged));
?>

Ausgabe/Werte mit einer Anzahl von drei sind die gewünschten

Array
(
    [1001] => 2
    [1002] => 3
    [1003] => 3
    [1004] => 3
    [1005] => 3
    [1006] => 1
)
0
jaymz

Dieses Problem kann in zwei Aufgaben aufgeteilt werden. Die erste Aufgabe besteht darin, alle Kombinationen (n ^ 2-n)/2 zu finden. Für n = 1000 ist die Lösung x = 499500. Die zweite Aufgabe besteht darin, alle x-Nummern durchzugehen und sie mit der Funktion doBla () zu vergleichen.

function getWayStr(curr) {
 var nextAbove = -1;
 for (var i = curr + 1; i < waypoints.length; ++i) {
  if (nextAbove == -1) {
    nextAbove = i;
   } else {
     wayStr.Push(waypoints[i]);
     wayStr.Push(waypoints[curr]);
   }
  }
  if (nextAbove != -1) {
    wayStr.Push(waypoints[nextAbove]);
    getWayStr(nextAbove);
    wayStr.Push(waypoints[curr]);
  }
 } 
0
Bytemain

Dieser Code ruft doBla() einmal für jedes Mal auf, wenn ein Wert in $numbers1 in $numbers2 gefunden wird:

// get [val => occurences, ...] for $numbers2
$counts = array_count_values($numbers2);
foreach ($numbers1 as $n1) {
    // if $n1 occurs in $numbers2...
    if (isset($counts[$n1])) {
        // call doBla() once for each occurence
        for ($i=0; $i < $counts[$n1]; $i++) {
            doBla();
        }
    }
}

Wenn Sie doBla() nur einmal aufrufen müssen, wenn eine Übereinstimmung gefunden wird:

foreach ($numbers1 as $n1) {
    if (in_array($n1, $numbers2))
        doBla();
}

Wenn $numbers1 und $numbers2 nur eindeutige Werte enthalten oder die Häufigkeit, mit der ein bestimmter Wert in beiden Arrays auftritt, nicht wichtig ist, erledigt array_intersect() die Aufgabe:

$dups = array_intersect($numbers1, $numbers2);
foreach ($dups as $n)
    doBla();

Ich stimme einigen früheren Beiträgen zu, dass die Aufrufe an doBla() wahrscheinlich mehr Zeit in Anspruch nehmen als das Durchlaufen der Arrays.

0
gregjor

Verwenden Sie WebAssembly anstelle von JavaScript.

0
Hasan Savran
  1. Erstellen Sie zwei doppelte Sammlungen, vorzugsweise solche mit schnellen Suchzeiten, wie HashSet oder vielleicht TreeSet. Vermeiden Sie Listen, da sie sehr schlechte Suchzeiten haben.

  2. Wenn Sie Elemente finden, entfernen Sie sie aus beiden Sätzen. Dies kann die Nachschlagzeit reduzieren, da weniger Elemente für spätere Suchen verwendet werden müssen.

0
Edwin Buck

Wenn Sie versuchen, eine Liste von Nummern ohne Duplikate zu erhalten, können Sie einen Hash verwenden:

$unique = array();
foreach ($list1 as $num) {
  $unique[$num] = $num;
}
foreach ($list2 as $num) {
  $unique[$num] = $num;
}
$unique = array_keys($unique);

Es wird etwas (sehr leicht) langsamer sein als die Array-Walk-Methode, aber meiner Meinung nach ist es sauberer.

0
brianloveswords

Wäre es möglich, diese Zahlen in zwei Datenbanktabellen einzugeben und dann einen INNER JOIN auszuführen? Dies ist sehr effizient und liefert nur die Nummern, die in beiden Tabellen enthalten sind. Dies ist eine perfekte Aufgabe für eine Datenbank.

0
m.edmondson