Sortieren Sie Algorithmen, die mit großen Datenmengen arbeiten

12

Ich suche nach Sortieralgorithmen, die mit einer großen Datenmenge arbeiten können, dh die auch dann funktionieren, wenn nicht der gesamte Datensatz gleichzeitig im Hauptspeicher gespeichert werden kann.

Der einzige Kandidat, den ich bisher gefunden habe, ist die Sortierung nach Zusammenführung: Sie können den Algorithmus so implementieren, dass er Ihren Datensatz bei jeder Zusammenführung durchsucht, ohne alle Daten gleichzeitig im Hauptspeicher zu speichern. Die Variation der Zusammenführungssorte, die ich im Auge habe, wird in diesem Artikel im Abschnitt Verwenden mit Bandlaufwerken beschrieben .

Ich halte dies für eine gute Lösung (mit der Komplexität O (nx log (n))), bin aber gespannt, ob es andere (möglicherweise schnellere) Sortieralgorithmen gibt, die für große Datenmengen geeignet sind, die nicht in den Hauptspeicher passen.

BEARBEITEN

Hier sind einige weitere Details, wie in den Antworten gefordert:

  • Die Daten müssen regelmäßig sortiert werden, z. B. einmal im Monat. Ich muss nicht einige Datensätze einfügen und die Daten inkrementell sortieren lassen.
  • Meine Beispieltextdatei hat ungefähr 1 GB UTF-8-Text, aber ich wollte das Problem generell lösen, auch wenn die Datei beispielsweise 20 GB groß wäre.
  • Es befindet sich nicht in einer Datenbank und kann aufgrund anderer Einschränkungen nicht vorhanden sein.
  • Die Daten werden von anderen als Textdatei gespeichert, ich habe meinen eigenen Code, um diese Textdatei zu lesen.
  • Das Format der Daten ist eine Textdatei: Neue Zeilenzeichen sind Satztrennzeichen.

Eine mögliche Verbesserung bestand darin, die Datei in Dateien aufzuteilen, die klein genug sind, um im Speicher sortiert zu werden, und schließlich alle diese Dateien mit dem oben beschriebenen Algorithmus zusammenzuführen.

Giorgio
quelle
1
Welche Art von Daten? Unterschiedliche Datensätze können unterschiedliche Algorithmen bedeuten, die am besten zu Ihrem Zweck passen.
Whatsisname
Es ist eine Textdatei und ich muss die Zeilen sortieren. Zeilen haben keine feste Länge, die Länge variiert jedoch nicht zu stark (etwa 50 Zeichen pro Datensatz).
Giorgio
3
Ich kenne Ihre Umgebung oder Ihre Einschränkungen nicht, aber ich würde eine Datenbank zum Sortieren verwenden, wann immer dies möglich ist. Dies liegt daran, dass es fast 100% fehlerfrei ist und wesentlich effizienter als mein Code ist.
NoChance
Ich arbeite an Linux / Java. Ich habe Merge Sort implementiert und es scheint ziemlich reibungslos zu funktionieren. Das Sortieren von mehreren Millionen Zeilen dauert ziemlich lange, aber ich muss das nur ab und zu tun.
Giorgio
@Giorgio, es ist gut, dass du einen solchen Algorithmus implementiert hast. Für die Produktion empfehle ich weiterhin die Verwendung einer Datenbank. Nicht nur wegen der Geschwindigkeit, sondern auch wegen der Zuverlässigkeit und Wartungsfreundlichkeit.
NoChance

Antworten:

13

Der kanonische Verweis auf Sortieren und Suchen ist Knuth, Vol. 3 . Fang dort an.

Das Buch wurde ursprünglich geschrieben, als Computer viel kleiner und langsamer waren als heute, was Sortiertechniken außerhalb des Arbeitsspeichers wichtiger machte, als sie heute wahrgenommen werden.

John R. Strohm
quelle
2
Danke für den Hinweis: Ich bin mir fast sicher, dass ich in Knuths Buch interessantes Material finden werde. Ich bin mir nicht sicher, ob Out-of-Memory-Sortiertechniken heute nicht relevant sind. Vielleicht nicht für alltägliche Aufgaben, aber ich kann mir vorstellen, dass es immer noch viele Situationen gibt, in denen sehr große Datenmengen verarbeitet werden müssen.
Giorgio
Knuths Algorithmen sind immer hilfreich. Beispielsweise kann eine Zusammenführungssortierung mit einem Heap-Sortierpuffer sehr effektiv und SEHR einfach zu implementieren sein.
Sulthan
4
Keine sehr nützliche Antwort, da das betreffende Material nicht kostenlos ist. Für das OP schlage ich vor, nach einer Antwort zu googeln. Sie müssen nicht 50 Dollar schälen, um ein Buch zu bekommen, wenn Sie diese Art von Informationen im Internet suchen. Natürlich können Sie dies wahrscheinlich auch kostenlos von ( ahem ) bestimmten Websites herunterladen . Kaum eine akzeptierte Antwort verdient.
Thomas Eding
1
@ThomasEding, es gibt solche "Bibliotheken", die große Mengen dieser veralteten Informationsspeicher- und -abrufgeräte enthalten, die "Bücher" genannt werden. "Bibliotheken" stellen "Bücher" kostenlos zur Verfügung. Wenn Ihre bestimmte "Bibliothek" nicht über das gewünschte "Buch" verfügt, bieten sie auch einen KOSTENLOSEN Service namens "Fernleihe" an, mit dem die "Bibliothek" das "Buch" von einer anderen "Bibliothek" ausleihen kann Leih es dir.
John R. Strohm
6

Externe R-Way-Zusammenführung wie im UNIX- sortBefehl ist eine gute Alternative. Nach Ihrer Formulierung bin ich mir nicht sicher, ob dies der Algorithmus ist, den Sie mit "Sortieren zusammenführen" gemeint haben, und wenn Sie ihn nicht kennen, schauen Sie ihn sich an.

Thiton
quelle
Vielen Dank. Die externe R-Way-Zusammenführung scheint anders zu sein, als ich es mir vorgestellt habe. Interessante Lektüre.
Giorgio
4

Ohne weitere Details ist "Sortierung zusammenführen" wahrscheinlich die beste Antwort, die Sie erhalten, Sie können jedoch je nach Ihren Anforderungen etwas viel schlaueres implementieren.

Können Sie zum Beispiel einfach einen speicherinternen Index der Datei erstellen und dann alle Werte auf einmal kopieren, um die Position der verschiedenen Schlüsselwerte zwischenzuspeichern? Passt 1/2 auf einmal in den Speicher oder 1/1000000? Wenn es der zweite ist, können Sie möglicherweise keinen Index in den Speicher einpassen. Wenn Sie beim ersten die beiden Hälften effizienter sortieren und dann in einem einzigen letzten Schritt zusammenführen.

Zum Teufel, da Sie nicht angegeben haben, ist es möglich, dass sich Ihre Daten alle in einer Datenbank befinden. Wenn ja, können Sie einfach eine Indextabelle erstellen und als gut bezeichnen (ich nehme an, dass dies nicht der Fall ist, aber darauf hinweisen Ihre Situation ist entscheidend für die Lösung eines so komplizierten Problems.

Wenn du es nur einmal machen willst und nach einem sehr schnellen Hack suchst, klingt es so, als wäre diese externe Merge-Sortierung ein guter Anfang, wenn du Unix verwendest (da es anscheinend eingebaut ist).

Wenn Sie die Reihenfolge beibehalten müssen und immer einen einzelnen Datensatz hinzufügen, ist eine Einfügesortierung erforderlich (das Hinzufügen eines einzelnen Datensatzes zu sortierten Daten ist immer eine Einfügesortierung).

Können Sie den Code steuern, der die Daten "liest"? Wenn ja, dann helfen viele Formen der Indizierung (anstatt durch Verschieben von Daten auf der Festplatte zu sortieren) VIEL (wird tatsächlich eine absolute Voraussetzung sein).

So:

  • An Ort und Stelle oder mehrere Dateien?
  • Einmal, regelmäßig oder immer sortiert?
  • Wie viel größer als der Arbeitsspeicher (wie viele Arbeitsspeicher werden für den gesamten Datensatz benötigt)?
  • Ist es in einer Datenbank? Kann es sein?
  • Steuern Sie den Code, der die Daten liest, oder werden andere eine Datei direkt sichern?
  • Datei Format? (Text? Feste Aufzeichnung?)
  • Andere besondere Umstände, nach denen ich nicht gefragt habe?
Bill K
quelle
Danke für die Antwort. Was meinst du mit "In place oder multiple record"?
Giorgio
Entschuldigung, sollte meine Antwort Korrektur gelesen haben - ich meinte mehrere Dateien. In-Place setzt im Wesentlichen festgelegte Datensatzgrößen und die Indizierung voraus, an welcher Stelle Sie wahrscheinlich eine Datenbank benötigen würden.
Bill K
Nein, es ist nicht vorhanden: Datensätze haben keine feste Größe. Ich verwende vier temporäre Dateien für meine aktuelle Implementierung.
Giorgio
Können Sie die Ausgabe mit Code interpretieren oder muss sie in einem bestimmten Format vorliegen (flache Textdatei?)? Wie oft muss sie sortiert werden - jedes Mal, wenn etwas hinzugefügt wird oder nur gelegentlich? Wenn etwas hinzugefügt wird, wird es einfach an das Ende angehängt, oder können Sie den Code schreiben, der es hinzufügt?
Bill K
Jede Zeile kann in einen Datensatz zerlegt werden (die Datei ist eine CSV-Datei), aber die meisten Felder sind Textfelder. Es muss von Zeit zu Zeit sortiert werden (z. B. jeden Monat) und es dauert ungefähr 1 Stunde, um mit meiner aktuellen Implementierung zu sortieren. Zum Einfügen einer Zeile könnte ich den Code schreiben, der die Zeile an der richtigen Stelle einfügt: Mit dem Code, den ich bisher habe, würde ich 20 Minuten brauchen, um ein solches Tool zu schreiben.
Giorgio
3

Wenn Sie wirklich eine skalierbare Lösung wünschen, sollten Sie sich TeraSort ansehen, die Standard-Sortierimplementierung mit Kartenreduzierung. Weitere Details zu StackOverflow .

m3th0dman
quelle
1
+1: Interessanter Link. Ist "Sortieren zusammenführen" nicht ein Beispiel für "Zuordnen / Reduzieren", bei dem "Zuordnen" dem Sortieren von Unterlisten und "Reduzieren" dem Zusammenführen entspricht?
Giorgio
Es mag so aussehen, aber Sie können Hadoop verwenden, um dies für Sie zu tun, anstatt es selbst zu schreiben.
m3th0dman
1

Möglicherweise interessieren Sie sich für eine Eimersorte . Die durchschnittliche Fallleistung ist die lineare Zeit.

= O (n + d) n: Anzahl der Elemente und d = Länge der größten Anzahl, wenn Sie eine Ahnung von Ihren Daten haben, d. H. Wenn Sie wissen, wie viele "Ziffern" lang sind, ist Ihre größte Zahl. Wenn Sie also 2 Millionen 6-stellige Zahlen => 0 (n) haben, ist dies linear.

Steinmetalle
quelle
0

Verwenden Sie einen externen Sortieralgorithmus für Zusammenführungen (wenn Ihre Daten kontinuierlich sind) oder eine Bucket-Sortierung mit Zählsortierung als Implementierung der Sortierung für Buckets (wenn Ihre Daten diskret und gleichmäßig verteilt sind).

Der wahrscheinlich beste Ansatz ist es, eine eigene Index- / Zuordnungsdatei zu erstellen, wenn das Inkrement klein ist.

  1. Irgendwie bestellen Sie Ihre "Datenbank"
  2. Weisen Sie jedem Eintrag eine Ganzzahl zu (1, 2, 3, 4, ..., n) (besser: Verwenden Sie einige spärliche Indizes)
  3. Wenn Sie ein Inkrement hinzufügen, müssen Sie nur eine Lücke finden, in der die linke Zahl kleiner oder gleich ist und die rechte Zahl größer oder gleich ist.
  4. Fügen Sie ein, während die Lücken ausreichend groß sind, wenn nicht: einfach neu indizieren (nie wieder sortieren) :-)
malejpavouk
quelle
0

Ich habe gerade einige abstrakte Strukturen namens "Big Queue" und "Big Array" erstellt, um das Sortieren und Suchen von Big Data auf einer einzelnen Maschine mit begrenztem Speicher zu vereinfachen. Grundsätzlich ähnelt der verwendete Algorithmus dem oben erwähnten - externe Zusammenführungssortierung.

Ich kann 128 GB Daten (jedes Element 100 Byte) in 9 Stunden auf einer einzelnen Maschine sortieren und dann die sortierten Daten fast ohne Zeitaufwand binär durchsuchen.

Hier ist ein Beitrag zum Durchsuchen von Big Data mithilfe meiner Open Source Big Queue und Big Array-Strukturen.

Bulldogge
quelle