Es ist in Abschnitt 2.6 und Problem 2, das ursprüngliche Problem ist wie folgt:
"Gibt es eine sequentielle Datei mit 4.300.000.000 32-Bit-Ganzzahlen, wie können Sie eine finden, die mindestens zweimal erscheint?"
Meine Frage zu dieser Übung lautet: Was sind die Tricks des obigen Problems und welche Art von allgemeiner Algorithmuskategorie ist dieses Problem?
Erzeuge ein Bit-Array der Länge 2 ^ 32 Bits (initialisiere auf Null), das wäre ungefähr 512MB und würde auf jedem modernen Rechner in den RAM passen.
Beginne das Lesen der Datei, int mit int, überprüfe das Bit mit dem gleichen Index wie der Wert von int, wenn das Bit gesetzt ist, hast du ein Duplikat gefunden, wenn es Null ist, setze eins und fahre mit dem nächsten int fort aus der Datei.
Der Trick besteht darin, eine geeignete Datenstruktur und einen geeigneten Algorithmus zu finden. In diesem Fall passt alles in den RAM mit einer geeigneten Datenstruktur und ein einfacher und effizienter Algorithmus kann verwendet werden Wenn die Zahlen int64 sind, müssen Sie eine geeignete Sortierstrategie finden oder mehrere Durchgänge durchführen, je nachdem, wie viel zusätzlichen Speicher Sie zur Verfügung haben.
Das Taubenschlag-Prinzip - Wenn Sie N Tauben in M Fächer haben, und N & gt; M, dann sind mindestens zwei Tauben in einem Loch. Der Satz von 32-Bit-Ganzzahlen sind unsere 2 ^ 32 Fächer, die 4,3 Milliarden Zahlen in unserer Akte sind die Tauben. Seit 4.3x10 ^ 9 & gt; 2 ^ 32, wir wissen, dass es Duplikate gibt.
Sie können dieses Prinzip anwenden, um zu testen, ob ein Duplikat, das wir suchen, eine Untermenge der Zahlen auf Kosten des Lesens der gesamten Datei ist, ohne mehr als ein wenig nach dem anderen in RAM zu laden - zählen Sie einfach wie oft eine Zahl in Ihrem Testbereich angezeigt wird, und vergleichen Sie sie mit der Gesamtzahl der ganzen Zahlen in diesem Bereich. Zum Beispiel, um nach einem Duplikat zwischen 1.000.000 und 2.000.000 inklusive zu suchen:
%Vor%Die Auswahl, wie groß die zu überprüfenden Bereiche sein sollen, und wie oft Sie 16 GB Daten lesen möchten, bleibt Ihnen überlassen:)
Soweit es eine allgemeine Algorithmuskategorie betrifft, ist dies ein kombinatorisches Problem (Mathematik über das Zählen).
Ich habe auch nach dem gleichen Ding gesucht und bin auf diesen [Link] gestoßen: Ссылка dachte daran, dasselbe zu teilen.
Was meinst du mit 32 Bit positiven ganzen Zahlen? Ich denke, dieses Problem erfordert keinen speziellen Algorithmus oder Trick zu lösen. Nur eine einfache Beobachtung wird zu der beabsichtigten Lösung führen.
Meine Beobachtung läuft so, die sequentielle Datei wird nur enthalten 32-Bit-Ganzzahlen (das ist von 0 bis 2 ^ 31 - 1). Angenommen, Sie setzen alle von ihnen In dieser Datei werden Sie mit 2 ^ 31 Zeilen enden. Du kannst sehen Wenn Sie diese positiven ganzen Zahlen noch einmal eingeben, erhalten Sie 2 ^ 31 * 2 Zeilen und es ist kleiner als 4.300.000.000.
Also ist die Antwort die ganzen positiven ganzen Zahlen von 0 bis 2 ^ 31 - 1.
Sortieren Sie die ganzen Zahlen und durchlaufen Sie sie, um zu sehen, ob aufeinanderfolgende ganze Zahlen Duplikate sind. Wenn Sie dies im Speicher tun möchten, benötigt es 16 GB Speicher, der mit den heutigen Maschinen möglich ist. Wenn dies nicht möglich ist, können Sie die Zahlen mithilfe von Mergesort sortieren und Zwischenarrays auf Festplatte speichern.
Mein erster Implementierungsversuch wäre, die Befehle sort und uniq von Unix zu verwenden.
Tags und Links algorithm programming-pearls