Sortieren von 20 GB Daten

Ich denke, ein Weg zu gehen ist Mergesort , es ist ein großartiger Algorithmus zum Sortieren eines große Menge an festen Datensätzen mit begrenztem Speicher.

Allgemeine Idee:

• liest N Zeilen aus der Eingabedatei (ein Wert, mit dem Sie die Zeilen im Speicher behalten können)
• sortiere diese Zeilen und schreibe die sortierten Zeilen in Datei 1

• Wiederholen Sie mit den nächsten N Zeilen, um Datei 2 zu erhalten

  ...

• Sie erreichen das Ende der Eingabedatei und Sie haben jetzt M Dateien (die jeweils sortiert sind)

• Verschmelzen Sie diese Dateien in einer einzigen Datei (Sie müssen dies auch in Schritten tun)

Sie könnten auch eine Lösung in Erwägung ziehen, die auf einer eingebetteten Datenbank basiert, z. Firebird embedded : Es funktioniert gut mit Delphi / Windows und Sie müssen nur einige DLL in Ihrem Programmordner hinzufügen (ich bin mir nicht sicher über Lazarus / OSX ).

Wenn Sie nur einen Bruchteil der gesamten Daten benötigen, scannen Sie die Datei sequenziell und behalten Sie nur die für die Anzeige erforderlichen Einträge bei. F.I. Nehmen wir an, Sie brauchen nur 300 Einträge von 1 Million. Scannen Sie die ersten 300 Einträge in der Datei und sortieren Sie sie im Speicher. Dann überprüfen Sie für jeden verbleibenden Eintrag, ob es niedriger als der niedrigste im Speicher ist und überspringen Sie es. Wenn es höher als der niedrigste Eintrag im Speicher ist, füge es an der richtigen Stelle in den 300 ein und wirf den niedrigsten weg. Dies wird den zweitniedrigsten zum niedrigsten machen. Wiederholen bis zum Ende der Datei.

Bitte hier eine Klasse finden, die eine Datei mit einer leicht optimierten Zusammenführungs-Sortierung sortiert. Das habe ich vor ein paar Jahren zum Spaß geschrieben. Es verwendet eine Skip-Liste zum Sortieren von Dateien im Speicher.

Edit: Das Forum ist deutsch und du musst dich registrieren (kostenlos). Es ist sicher, erfordert aber ein wenig Deutschkenntnisse.

In der Vergangenheit musste ich mit großen Dateien arbeiten, irgendwo im Bereich von 0,1-3 GB. Es wurden nicht alle 'Spalten' benötigt, daher war es in Ordnung, die restlichen Daten in den RAM zu schreiben. Jetzt muss ich mit Dateien im Bereich 1-20GB arbeiten, und sie werden wahrscheinlich mit der Zeit wachsen. Das ist völlig anders, weil Sie die Daten nicht mehr in den Arbeitsspeicher laden können.

Meine Datei enthält mehrere Millionen Einträge (ich habe einen mit 30 mil Einträgen gefunden). Bei der Eingabe besteht in etwa 10 'Spalten': eine Zeichenfolge (50-1000 Unicode-Zeichen) und mehrere Zahlen. Ich muss die Daten nach 'Spalte' sortieren und anzeigen. Für den Benutzer sind nur die oberen Einträge (1-30%) relevant, der Rest sind Daten niedriger Qualität.

Also brauche ich ein paar Vorschläge, in welche Richtung ich gehen soll. Ich möchte definitiv keine Daten in einer Datenbank ablegen, da sie schwer zu installieren und für Nicht-Computer-versierte Personen zu konfigurieren sind. Ich liefere gerne ein monolithisches Programm.

Das Anzeigen der Daten ist überhaupt nicht schwierig. Aber sortieren ... ohne die Daten im RAM zu laden, auf normalen PCs (2-6GB RAM) ... wird einige gute Stunden töten.

Ich habe ein wenig in MMF (Memory Mapped Files) gesucht, aber dieser Artikel von Danny Thorpe zeigt, dass es möglicherweise nicht passend ist: Ссылка

Also habe ich darüber nachgedacht, nur die Daten aus der Spalte zu laden, die in RAM und einem Zeiger auf die Adresse (in die Datei) des 'Eintrags' sortiert werden soll. Ich sortiere die 'Spalte', dann benutze ich den Zeiger, um den Eintrag zu finden, der jeder Spaltenzelle entspricht, und stelle den Eintrag wieder her. Die 'Wiederherstellung' wird direkt auf die Festplatte geschrieben, so dass kein zusätzlicher Arbeitsspeicher benötigt wird.

PS: Ich suche nach einer Lösung, die sowohl auf Lazarus als auch auf Delphi funktioniert, weil Lazarus (eigentlich FPC) 64 Bit Unterstützung für Mac hat. 64 Bit bedeutet mehr RAM verfügbar = schnelleres Sortieren.

Wenn Sie die Daten nicht in den Hauptspeicher einpassen können, befinden Sie sich in den Bereichen externe Sortierung . In der Regel handelt es sich dabei um eine externe Zusammenführungssortierung Sortieren Sie kleinere Datenblöcke einzeln nacheinander und schreiben Sie sie zurück auf die Festplatte. Und dann füge diese Chunks zusammen.

Ich denke, ein Weg zu gehen ist Mergesort , es ist ein großartiger Algorithmus zum Sortieren eines große Menge an festen Datensätzen mit begrenztem Speicher.

Allgemeine Idee:

• liest N Zeilen aus der Eingabedatei (ein Wert, mit dem Sie die Zeilen im Speicher behalten können)
• sortiere diese Zeilen und schreibe die sortierten Zeilen in Datei 1

• Wiederholen Sie mit den nächsten N Zeilen, um Datei 2 zu erhalten

  ...

• Sie erreichen das Ende der Eingabedatei und Sie haben jetzt M Dateien (die jeweils sortiert sind)

• Verschmelzen Sie diese Dateien in einer einzigen Datei (Sie müssen dies auch in Schritten tun)

Sie könnten auch eine Lösung in Erwägung ziehen, die auf einer eingebetteten Datenbank basiert, z. Firebird embedded : Es funktioniert gut mit Delphi / Windows und Sie müssen nur einige DLL in Ihrem Programmordner hinzufügen (ich bin mir nicht sicher über Lazarus / OSX ).

Wenn Sie nur einen Bruchteil der gesamten Daten benötigen, scannen Sie die Datei sequenziell und behalten Sie nur die für die Anzeige erforderlichen Einträge bei. F.I. Nehmen wir an, Sie brauchen nur 300 Einträge von 1 Million. Scannen Sie die ersten 300 Einträge in der Datei und sortieren Sie sie im Speicher. Dann überprüfen Sie für jeden verbleibenden Eintrag, ob es niedriger als der niedrigste im Speicher ist und überspringen Sie es. Wenn es höher als der niedrigste Eintrag im Speicher ist, füge es an der richtigen Stelle in den 300 ein und wirf den niedrigsten weg. Dies wird den zweitniedrigsten zum niedrigsten machen. Wiederholen bis zum Ende der Datei.

Bitte hier eine Klasse finden, die eine Datei mit einer leicht optimierten Zusammenführungs-Sortierung sortiert. Das habe ich vor ein paar Jahren zum Spaß geschrieben. Es verwendet eine Skip-Liste zum Sortieren von Dateien im Speicher.

Edit: Das Forum ist deutsch und du musst dich registrieren (kostenlos). Es ist sicher, erfordert aber ein wenig Deutschkenntnisse.

Wenn Sie die Daten nicht in den Hauptspeicher einpassen können, befinden Sie sich in den Bereichen externe Sortierung . In der Regel handelt es sich dabei um eine externe Zusammenführungssortierung Sortieren Sie kleinere Datenblöcke einzeln nacheinander und schreiben Sie sie zurück auf die Festplatte. Und dann füge diese Chunks zusammen.