Erstellen einer eindeutigen Liste aus Dataset zu groß, um in den Speicher zu passen

Question

Ich habe eine Liste von 120 Millionen Datensätze von etwa 40/50 Bytes, die etwa 5,5/6 Gigabyte rohen Speicherplatz, ohne zusätzlichen Speicherplatz, um ein zu halten Array im Speicher.

Ich möchte sicherstellen, dass diese Liste einzigartig ist. Die Art, wie ich es versucht habe, ist ein Hashset <String> zu erstellen und alle Einträge nacheinander hinzuzufügen.

Wenn ich zu etwa 33 Millionen Datensätze komme, habe ich keinen Speicher mehr und die Erstellung der Liste verlangsamt sich zu einem Crawl.

Gibt es eine bessere Möglichkeit, diese riesige Liste von Einträgen rechtzeitig zu sortieren? Die einzige Lösung, die ich mir vorstellen kann, ist die Verwendung einer Amazon EC2 High-Memory Quadruple Extra Large Instanz für eine Stunde.

Dank

Answer 1

Wenn Sie nur auf Eindeutigkeit zu überprüfen versuchen, würde ich einfach die Eingangssequenz in Eimer aufgespalten und dann jede Schaufel einzeln überprüfen. Wenn Sie zum Beispiel annehmen, dass Sie die Daten aus einer Datei laden, können Sie die Eingabe streamen und sie in 26 verschiedene Dateien schreiben, eine für jeden Buchstaben, mit dem der Datensatz beginnt (ich nehme jeden Datensatz naiv an) beginnt mit AZ - bitte passen Sie sich an Ihre reale Situation an. Dann können Sie jede dieser kleineren Dateien auf Eindeutigkeit überprüfen, indem Sie etwas wie Ihren vorhandenen Code verwenden - weil keiner von ihnen zu groß ist, um in den Speicher gleichzeitig zu passen. Das anfängliche Bucketing garantiert, dass es keine doppelten Einträge gibt, die sich in unterschiedlichen Buckets befinden.

Natürlich gibt es verschiedene Möglichkeiten, wie Sie das Bucketing durchführen können, und verschiedene Ansätze sind für verschiedene Datensätze effektiv. Sie könnten beispielsweise nach Hash-Code suchen - nehmen Sie die unteren 5 Bits des Hash-Codes, um 32 verschiedene Buckets zu erstellen. Das ist wahrscheinlich eine vernünftige gleiche Verteilung von Datensätzen zwischen Buckets, und macht keine Annahmen über die Eingabedaten. Ich erwähnte nur die "Nehmen Sie den ersten Buchstaben Ansatz" oben, da es eine einfachere Möglichkeit ist, das Konzept zu begreifen :)

Answer 2

Verwenden Sie bucket sort, um die Liste zu sortieren, einige der Inhalte der Eimer regelmäßig auf die Festplatte zu leeren, um zu vermeiden, dass sie ausgeht der Erinnerung. Laden Sie dann jeden einzelnen leeren Eimer der Reihe nach und verwenden Sie entweder Ihren HashSet-Ansatz oder sortieren Sie ihn und überprüfen Sie ihn auf diese Weise.

Answer 3

Sie könnten immer in einer SQLite-Datenbank mit einem eindeutigen Index arbeiten, da dies bei der weiteren Verarbeitung des Datensatzes helfen kann.