Sortieren Sie den Inhalt einer extrem großen (800 GB) Textdatei unter Windows

25

Ich habe eine Textdatei mit einem Wort in jeder Zeile, die Größe der Datei beträgt 800 GB. Ich muss die Wörter alphabetisch sortieren.

Ich habe versucht, das Windows- Sortierprogramm zu verwenden mit:

sort.exe input.txt /o output.txt

Das gibt den Fehler: Nicht genügend Hauptspeicher, um die Sortierung abzuschließen.

Ich habe also 32 GB RAM , wenn ich versuche, 10 GB Arbeitsspeicher für die Sortierung anzugeben:

sort.exe input.txt /o output.txt /M 10000000

Ich bekomme:

Warnung: Die angegebene Speichergröße wird auf den verfügbaren Paging-Speicher reduziert.

Eingabedatensatz überschreitet maximale Länge. Geben Sie ein größeres Maximum an.

Welche Möglichkeiten habe ich?

windows sorting Maya
quelle
2
Bitte nicht kreuzen. Siehe Ist das Weiterleiten einer Frage an mehrere Stack Exchange-Sites zulässig, wenn die Frage für jede Site thematisch ist?
DavidPostill
10
Dies ist kein Cross-Post. Ich bin kein Computer. Das Posten und Löschen des anderen dauert einige Minuten.
MaYaN
3
Erlaube
4
Unter Linux können Sie diese Methode anwenden . Mit Dateien von 100 MB sollte es kein großes Problem sein.
Eric Duminil
3
Welche Windows-Version verwenden Sie? Die Datei sort.exe mit dem relativ alten Windows Server 2012 R2 behauptet, externe Zusammenführungssortierungen mithilfe einer temporären Datei auf der Festplatte durchführen zu können (ohne eine Größenbeschränkung zu dokumentieren). Versuchen Sie, mit / T einen Datenträger mit 800 GB für die temporäre Datei anzugeben. Und die Meldung "Eingabedatensatz überschreitet maximale Länge" scheint keinen Bezug zum Leerzeichen zu haben - sehen Sie sich die / REC-Option an und überlegen Sie, was Ihr Zeilenabschluss ist.
Davidbak

Antworten:

16

Welche Möglichkeiten habe ich?

Probieren Sie das Freeware Command Line Sort Utility CMSort aus .

Es werden mehrere temporäre Dateien verwendet und am Ende zusammengeführt.

CMsort liest Datensätze einer Eingabedatei, bis der eingestellte Speicher erreicht ist. Dann werden die Datensätze sortiert und in eine temporäre Datei geschrieben. Dies wird wiederholt, bis alle Datensätze verarbeitet wurden. Schließlich werden alle temporären Dateien in die Ausgabedatei zusammengeführt. Wenn der verfügbare Speicher ausreicht, werden keine temporären Dateien geschrieben und es ist keine Zusammenführung erforderlich.

Ein Benutzer gibt an, eine Datei mit 130.000.000 Bytes sortiert zu haben.

Wenn Sie selbst Code optimieren möchten, gibt es auch die Option " Riesige Textdateien sortieren " - CodeProject - "Algorithmus zum Sortieren von Zeilen in Textdateien, deren Größe den verfügbaren Speicher überschreitet".

DavidPostill
quelle
26
Wow, 130 Megabyte !!! +1
David Foerster
3
@DavidPostill Sind Sie sicher, dass das Sortieren von Coreutils für Windows nicht effizienter ist ( --parallelOption, wenn Sie mehr als einen Core haben ...)?
Hastur
23

Eine andere Möglichkeit besteht darin, die Datei in eine Datenbank zu laden. EG MySQL und MySQL Workbench.
Datenbanken sind perfekte Kandidaten für die Arbeit mit großen Dateien

Wenn Ihre Eingabedatei nur Wörter enthält, die durch eine neue Zeile getrennt sind, sollte dies nicht zu schwierig sein.

Nachdem Sie die Datenbank und MySQL Workbench installiert haben, müssen Sie dies tun.
Erstellen Sie zuerst das Schema (dies setzt voraus, dass Wörter nicht länger als 255 Zeichen sind, obwohl Sie dies durch Erhöhen des Argumentwerts ändern können). Die erste Spalte "idwords" ist ein Primärschlüssel.

CREATE SCHEMA `tmp` ;

CREATE TABLE `tmp`.`words` (
  `idwords` INT NOT NULL AUTO_INCREMENT,
  `mywords` VARCHAR(255) NULL,
  PRIMARY KEY (`idwords`));

Zweitens importieren Sie die Daten: ZB Dies importiert alle Wörter in die Tabelle (dieser Schritt kann eine Weile dauern. Mein Rat wäre, zuerst einen Test mit einer kleinen Wortdatei durchzuführen, und wenn Sie sicher sind, dass das Format das gleiche ist wie der größere (kürzen Sie die Tabelle. IE Clear it out und laden Sie den vollständigen Datensatz).

LOAD DATA LOCAL INFILE "C:\\words.txt" INTO TABLE tmp.words
LINES TERMINATED BY '\r\n'
(mywords);


Dieser Link kann dabei helfen, das richtige Format für das Laden zu finden. https://dev.mysql.com/doc/refman/5.7/de/load-data.html
EG Wenn Sie die erste Zeile überspringen müssen, gehen Sie folgendermaßen vor.

LOAD DATA LOCAL INFILE "H:\\words.txt" INTO TABLE tmp.words
-- FIELDS TERMINATED BY ','
LINES TERMINATED BY '\r\n'
IGNORE 1 LINES
(mywords);

Speichern Sie schließlich die sortierte Datei. Dies kann auch abhängig von Ihrem PC eine Weile dauern.

SELECT tmp.words.mywords
FROM tmp.words
order by tmp.words.mywords asc
INTO OUTFILE 'C:\\sorted_words.csv';

Sie können die Daten auch nach Belieben durchsuchen. EG Dies gibt Ihnen die ersten 50 Wörter in aufsteigender Reihenfolge (ab dem 0. oder ersten Wort).

SELECT tmp.words.mywords
FROM tmp.words
order by tmp.words.mywords asc
LIMIT 0, 50 ;

Viel Glück,
Pete

Peter H
quelle
2
Das IST die richtige Antwort mit deutlichem Abstand.
MonkeyZeus
1
Dieser Ansatz ist definitiv flexibler, insbesondere wenn Sie feststellen, dass Sie die Sortierung beispielsweise mit einer anderen Reihenfolge wiederholen müssen.
Barbecue
Es ist mir egal, wie schnell Ihre Instanz von MySQL , MariaDB oder einem anderen DBMS ist, es wird nicht annähernd die Insert-Leistung von SQLite erreichen, das auf demselben Computer ausgeführt wird. Selbst mit etwas so schnellem wie SQLite ist diese Datenmenge zu viel (und zu langsam), um verarbeitet zu werden (vertrau mir, das habe ich zuerst versucht!). Die beste Lösung ist also, die Duplikate zuerst zu sortieren und zu entfernen und dann in eine Datenbank wie SQLite einzufügen . Während diese Lösung für einige Fälle gültig sein mag, ist sie sicherlich nicht für das, was ich versuche, zu tun. Vielen Dank, dass Sie sich die Zeit genommen haben, dies trotzdem zu posten.
MaYaN
Bestellung von mywordswird ewig dauern. Trotzdem LIMITwird es genauso lange dauern wie das Ganze, da MySQL jeden einzelnen Wert von durchlaufen mywordsund bestellen muss. Um dies zu beheben, müssen Sie nach Abschluss des Vorgangs die folgenden Schritte ausführen LOAD DATA. Fügen Sie einen Index zu hinzu mywords. Jetzt können Sie nach dieser Spalte bestellen, ohne dass es ein Jahrtausend dauert. Und es ist besser, den Index nach dem Laden der Daten hinzuzufügen, als zu dem Zeitpunkt, als Sie die Tabelle erstellt haben (viel schnelleres Laden der Daten).
Buttle Butkus
7

sort

Es gibt viele Algorithmen zum Sortieren geordneter und nicht geordneter Dateien [ 1 ] .
Da all diese Algorithmen bereits implementiert sind, wählen Sie ein bereits getestetes Programm aus.

In coreutils (von Linux, aber auch für Windows verfügbar [ 2 ] ) gibt es den sortBefehl, der unter Multi-Core-Prozessoren parallel ausgeführt werden kann: Normalerweise reicht er aus.

Wenn Ihre Datei so umfangreich ist , können Sie die Aufteilung ( split -l) der Datei in einige Abschnitte unterstützen, möglicherweise mithilfe der parallelen Option ( --parallel), und die resultierenden geordneten Abschnitte mit der -mOption sortieren ( Zusammenführungssortierung ).
Eine der vielen Möglichkeiten, dies zu tun, wird hier erläutert (Datei teilen, einzelne Chunks bestellen, geordnete Chunks zusammenführen, temporäre Dateien löschen).

Anmerkungen:

  • In Windows 10 gibt es das sogenannte Windows-Subsystem für Linux, in dem alle Linux-Beispiele natürlicher erscheinen.
  • Das Sortieren mit unterschiedlichen Algorithmen hat unterschiedliche Ausführungszeiten, die sich in Abhängigkeit von der Anzahl der zu sortierenden Dateneinträge (O (n m ), O ( n logn) ...) skalieren lassen.
  • Die Effizienz des Algorithmus hängt von der Reihenfolge ab, die bereits in der Originaldatei vorhanden ist.
    (Beispielsweise ist eine Blasensortierung der schnellste Algorithmus für eine bereits bestellte Datei - genau N -, in anderen Fällen ist sie jedoch nicht effizient).
Hastur
quelle
2

Um eine alternative Lösung für Peter H anzubieten, gibt es ein Programm q, das SQL-Befehle für Textdateien erlaubt. Der folgende Befehl würde dasselbe tun (von der Eingabeaufforderung in demselben Verzeichnis wie die Datei ausführen), ohne dass SQL Workbench installiert oder Tabellen erstellt werden müssen.

q "select * from words.txt order by c1"

c1 ist die Abkürzung für Spalte 1.

Sie können doppelte Wörter mit ausschließen

q "select distinct c1 from words.txt order by c1"

und senden Sie die Ausgabe an eine andere Datei

q "select distinct c1 from words.txt order by c1" > sorted.txt
Brian
quelle
Irgendeine Idee, ob dies mit einer 800-Gig-Datei fertig wird?
Rawling
1
Ich bin mir nicht 100% sicher - ich habe das oben beschriebene mit einer 1200-Zeilen-Datei (9 KB) getestet. Die Entwicklerseite enthält eine Seite mit "Einschränkungen", auf der keine Informationen zur maximalen Dateigröße angegeben sind. Eine große Datei kann immer noch auf ein Speicherproblem stoßen.
Brian
3
q kann diese Menge nicht verarbeitet von Daten nicht vergessen , dass q verwendet SQLite hinter der Szene , wenn ich nicht die Daten lenken laden kann SQLite , was machen Sie glauben , q können?
MaYaN
2

Wenn die Wörter in jeder Zeile aus einem begrenzten Wortschatz stammen (z. B. Englisch), können Sie die Liste mithilfe einer TreeMap und der Anzahl der Aufzeichnungen (wobei m die Anzahl der eindeutigen Werte ist) nach O (n + m log m) sortieren.

Andernfalls können Sie den Big-Sorter der Java-Bibliothek verwenden . Die Eingabe wird in sortierte Zwischendateien aufgeteilt und effizient zusammengeführt (gesamtes O (nlogn)). So sortieren Sie Ihre Datei:

Sorter.serializerTextUtf8()
      .input(inputFile)
      .output(outputFile)
      .loggerStdOut() // display some progress
      .sort();

Ich habe eine 1,7 GB-Datei (100 m Zeilen) mit zufällig generierten 16-Zeichen-Wörtern erstellt und wie oben in 142 Sekunden sortiert. Basierend auf der Berechnungskomplexität von O (n log n) der von mir verwendeten Methode schätze ich, dass 800 GB 16-Zeichen-Wörter enthalten würden Es dauert ungefähr 24 Stunden, um auf meinem i5 2.3GHz Laptop mit SSD Single-Thread zu sortieren.

Dave Moten
quelle