Sortieren von 20 GB Daten

In der Vergangenheit musste ich mit großen Dateien arbeiten, irgendwo in der 0,1-3GB-Bereich. 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 in 1-20GB Bereich arbeiten, und sie werden wahrscheinlich wachsen, wie die Zeit vergeht. Das ist völlig anders, weil Sie die Daten nicht mehr in den Arbeitsspeicher laden können.Sortieren von 20 GB Daten

Meine Datei enthält mehrere Millionen Einträge (ich habe eine mit 30 mil Einträge 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 darüber, 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 das Sortieren ... ohne die Daten im RAM zu laden, auf normalen PCs (2-6GB RAM) ... wird einige gute Stunden bringen.

Ich war ein wenig in MMF suchen (Memory Mapped-Dateien), aber in diesem Artikel von Danny Thorpe zeigt, dass es nicht geeignet sein kann: http://dannythorpe.com/2004/03/19/the-hidden-costs-of-memory-mapped-files/

Also, ich war über das Laden denken nur die Daten aus der Spalte, die in RAM und einem Zeiger auf die Adresse (in die Datei) des "Eintrags" sortiert werden muss. 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 bin auf der 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 = schnellere Sortierung.

Quelle

2014-04-03 Ampere

Obwohl es nicht Delphi-spezifisch ist, gibt es hier Dutzende von Posts zum Sortieren großer Textdateien. Suchen Sie nach 'sort large files' und sehen Sie sich die Ergebnisse an. Es gibt Links zu verschiedenen Techniken dafür, wie zum Beispiel die im ersten Ergebnis (http://stackoverflow.com/q/7918060). Wie gesagt, Ihre Frage ist sehr weit gefasst und ich bin mir nicht sicher, ob sie hier ohne Beispieldaten konkret beantwortet werden kann. –

Wenn Sie Ihre eigenen schreiben möchten, kann ich einen alten Mergesort-Code von einer Backup-CD ausgraben und irgendwo hochladen. Es ist jedoch DOS-Befehlszeilenmaterial. –

@ JanDoggen-Es spielt keine Rolle, es ist die Befehlszeile. Ich brauche es sowieso ohne GUI. Bereits gemachter Code ist immer willkommen. Danke vielmals. – Ampere

denke ich, ein Weg zu gehen Mergesort ist, es ist ein großer Algorithmus eine große Menge an festen Aufzeichnungen mit begrenztem Speicher für die Sortierung.

Allgemeine Idee:

lesen N Zeilen aus der Eingabedatei (ein Wert, der die Zeilen im Speicher halten können)
sortieren diese Zeilen und schreiben die sortierten Zeilen 1 bis Datei
Wiederholung mit den nächsten N Zeilen Datei 2

...
Sie erreichen das Ende des inp zu erhalten ut-Datei und Sie haben jetzt M-Dateien (von denen jede sortiert ist)
merge diese Dateien in einer einzigen Datei (Sie werden dies auch in Schritten zu tun haben)

Sie könnten Betrachten Sie auch eine Lösung basierend auf einer eingebetteten Datenbank, zFirebird embedded: es funktioniert gut mit Delphi/Windows und Sie müssen nur einige DLL in Ihrem Programmordner hinzufügen (ich bin nicht sicher über Lazarus/OSX).

Quelle

2014-04-03 20:05:17 manlio

+1 für die Datenbankempfehlung. Bei diesem Umfang (einzelne GBs bis einzelne TBs) bietet das relationale Modell viele, viele Vorteile gegenüber jedem flachen Dateischema, das Sie finden oder schaffen werden. Viel größer als das und die Dinge werden immer kniffliger, aber im Moment ist eine Datenbank einfach der beste Weg. –

http://forum.lazarus.freepascal.org/index.php?topic=4159.0 diskutiert einige eingebettete DBs für die Verwendung mit Lazarus, was bedeutet, dass SQLite als Firebird eine Anforderung für .NET hat. Laut http://sqlite.org/limits.html hat sqlite eine Größenbeschränkung von 2^64 Zeilen und mehrere Terabytes an Daten, also sollte man mit seinen Grenzen zurechtkommen.Aus dem Speicher ist die Installation auf eine DLL beschränkt, die mit Ihrer exe bereitgestellt wird, und die größten Einschränkungen sind mit dem Threading und der Freigabe Ihrer Verbindung verbunden, von denen Sie keine hervorgehoben haben –

Ich mochte die Idee einer DB nicht, aber seit Firebird ist eingebettet Ich fange an darüber nachzudenken, es zu benutzen! Vielen Dank! – Ampere

Wenn Sie die Daten nicht in den Hauptspeicher passen, dann sind Sie in den Bereichen external sorting. In der Regel handelt es sich hierbei 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.

Quelle

2014-04-03 20:01:53

Ich war sicher, dass es dafür einen technischen Namen (und Algorithmus) geben musste. Vielen Dank, ich werde einen Blick darauf werfen. – Ampere

Wenn Sie nur einen Bruchteil der gesamten Daten benötigen, scannen Sie die Datei sequenziell und behalten Sie nur die zur Anzeige benötigten 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.

Quelle

2014-04-03 21:44:24

Netter Vorschlag, aber bis zu 30% von 20GB ist immer noch ein großer Teil der Daten zu halten, geschweige denn blies Ihre 32-Bit-Mem-Limit (bestätigen Sie die Erwähnung von 64-Bit im OP) –

@MattAllwood, natürlich es hängt von den tatsächlich benötigten Daten ab, aber da Daten für den Benutzer dargestellt werden, bezweifle ich, dass 30% von 1 Million Einträge tatsächlich sichtbar sind. Das möchte ich mir definitiv nicht ansehen. –

@ UweRaabe-Über den GUI-Teil: Die Daten müssen dem Benutzer präsentiert werden, aber das ist überhaupt kein Problem. Ich kann ein Stringgrid verwenden und 100 Zeilen (oder was auch immer auf den Bildschirm passt) anzeigen und die Daten nur für diese 100 Zeilen in den Speicher laden. Während der Benutzer scrollt, entlade ich die alten Daten und lade neue Daten ein. Zur Visualisierung ist der mem-Footprint also nahezu leer. – Ampere

Wirklich, es gibt keine Sortieralgorithmen, die 30g von zufällig sortierten Daten schnell bewegen können.

Wenn Sie auf mehrere Arten sortieren müssen, besteht der Trick nicht darin, die Daten selbst zu verschieben, sondern stattdessen einen Index für jede Spalte zu erstellen, die Sie sortieren müssen.

Ich mache es so mit Dateien, die auch Dutzende Gigabyte lang sind, und Benutzer können die Daten sortieren, scrollen und durchsuchen, ohne zu bemerken, dass es sich um ein riesiges Dataset handelt, mit dem sie arbeiten.

Quelle

2014-04-04 06:07:56

irgendwelche Beispiele für eine solche Implementierung? Wie erhalten Sie einen Index, der die zu sortierenden Daten darstellen würde? Angenommen, ich möchte alphabetisch sortieren oder nach der Länge der Zeichenfolge in der Spalte sortieren. Dann gibt es 2 verschiedene Sortierwerte: 1. alphabetisch und 2. Länge. TIA –

Die einfachste Form ist ein Array mit der gleichen Anzahl von Elementen, die Sie in Ihrem Dataset haben. Das Array ist eine Liste von (Wert, Index). Dieser Index selbst ist sortiert. Anhand dieses Indexes können Sie leicht die Daten finden, die damit übereinstimmen. Wenn Sie alle Elemente benötigen, die mit einem B beginnen, suchen Sie Ihren sortierten Index, und Sie finden dort heraus, wo Sie die ganzen Tupel auf der Festplatte finden können. Wenn Sie viele Einfügungen und Löschungen durchführen, möchten Sie möglicherweise eine verknüpfte Liste anstelle eines einfachen Arrays verwenden. Alternativ können Sie, anstatt alles selbst zu implementieren, eine Datenbank verwenden. 20 GB sind Erdnüsse für den durchschnittlichen db. –

Bitte finden Sie here a class, die eine Datei mit einem leicht optimierten merge sort 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 Sie müssen sich registrieren (kostenlos). Es ist sicher, erfordert aber ein bisschen Deutschkenntnisse.

Quelle

2014-04-04 08:09:04 alzaimar

Sie müssen sich kostenlos registrieren. Es ist die größte deutsche Delphi-Website, man kümmert sich nicht um Mails oder ähnliches. Einen Besuch wert und englische Fragen werden ebenfalls beantwortet. Du wärst überrascht, beide englisch sprechenden Deutschen dort zu treffen ;-) – alzaimar

Hmm. Ich habe diese Klasse geschrieben. Jede Chance, es dir zu geben? – alzaimar

Wurde der Code für Delphi 7 (oder eine andere Nicht-Unicode-Version von Delphi) geschrieben? Das Programm stürzt (wie es ist) in der Funktion TcsStringSkipList.CompareKeys ab. Heute Abend ist spät. Ich werde versuchen, morgen herauszufinden, wie funktioniert und warum es abstürzt. – Ampere

Sortieren von 20 GB Daten

Antwort

Verwandte Themen