☰

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

tag-icon • tag-icon windows sorting
Sortieren Sie den Inhalt einer extrem großen (800 GB) Textdatei unter Windows

Ich habe einTextDatei mit einem Wort in jeder Zeile, die Dateigröße beträgt 800 GB. Ich muss die Wörter alphabetisch sortieren.

Ich habe versucht, mit demWindows SortierenProgramm mit:

sort.exe input.txt /o output.txt

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

Ich habe 32 GBRAMWenn ich also versuche, 10 GB Speicher für die Sortierung anzugeben, verwende ich:

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

Ich bekomme:

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

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

Welche Möglichkeiten habe ich?

Antwort1

Welche Möglichkeiten habe ich?

VersuchenKostenloses Befehlszeilen-Sortierprogramm CMSort.

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

CMsort liest Datensätze einer Eingabedatei, bis der eingestellte Speicher erreicht ist. Anschließend werden die Datensätze sortiert und in eine temporäre Datei geschrieben. Dieser Vorgang wird so lange wiederholt, bis alle Datensätze verarbeitet sind. Abschließend werden alle temporären Dateien in die Ausgabedatei integriert. Wenn der verfügbare Speicher ausreichend ist, werden keine temporären Dateien geschrieben und es ist kein Zusammenführen erforderlich.

Ein Benutzer berichtet, dass er eine Datei mit 130.000.000 Bytes sortiert hat.

Wenn Sie den Code selbst optimieren möchten, gibt es auchSortieren großer Textdateien - CodeProject- „Algorithmus zum Sortieren von Zeilen in Textdateien, deren Größe den verfügbaren Speicher überschreitet“

Antwort2

Eine weitere Möglichkeit besteht darin, die Datei in eine Datenbank zu laden. Beispielsweise MySQL und MySQL Workbench.
Datenbanken eignen sich perfekt für die Arbeit mit großen Dateien.

Wenn Ihre Eingabedatei nur durch eine neue Zeile getrennte Wörter enthält, sollte dies nicht allzu schwierig sein.

Nachdem Sie die Datenbank und MySQL Workbench installiert haben, müssen Sie Folgendes tun.

Erstellen Sie zunächst das Schema (dabei wird davon ausgegangen, dass die 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.
Dadurch werden beispielsweise alle Wörter in die Tabelle importiert. Dieser Schritt kann eine Weile dauern. Ich würde Ihnen raten, zunächst einen Test mit einer kleineren Datei durchzuführen und erst dann, wenn Sie sicher sind, dass das Format mit dem der größeren übereinstimmt, die Tabelle zu kürzen, d. h. sie zu löschen und den vollständigen Datensatz zu laden.

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 die Ladung zu finden. https://dev.mysql.com/doc/refman/5.7/en/load-data.html

Wenn Sie beispielsweise die erste Zeile überspringen müssten, gehen Sie wie folgt vor.

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

Zum Schluss speichern Sie die sortierte Datei. Dies kann je nach 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 beliebig durchsuchen.
So erhalten Sie beispielsweise die ersten 50 Wörter in aufsteigender Reihenfolge (beginnend bei der Nullposition bzw. dem ersten Wort).

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

Antwort3

sort

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

InKernel-Dienstprogramme (von Linux, aber auch für Windows verfügbar [2] ), gibt es einen sortBefehl, der die parallele Ausführung unter Mehrkernprozessoren ermöglicht: Normalerweise reicht das aus.

Wenn Ihre Dateiso riesigSie können die Verarbeitung unterstützen split -l, indem Sie die Datei in mehrere Teile aufteilen ( ), ggf. mit der Option „Parallel“ ( --parallel), und die resultierendengeordnete Stückemit der -mOption (Zusammenführen, sortieren).
Eine der vielen Möglichkeiten, dies zu tun, wird erklärtHier(Datei aufteilen, einzelne Blöcke ordnen, geordnete Blöcke zusammenführen, temporäre Dateien löschen).

Anmerkungen:

  • In Windows 10 gibt es die sog.Windows-Subsystem für Linuxin der alle Linux-Beispiele natürlicher erscheinen.
  • Das Sortieren mit verschiedenen Algorithmen hat unterschiedliche Ausführungszeiten, die von der Anzahl der zu sortierenden Dateneinträge abhängen (O(n m ), O(nlogn)...).
  • Die Effizienz des Algorithmus hängt von der Reihenfolge ab, die bereits in der Originaldatei vorhanden ist.
    (Beispiel:Blasensortierungist der schnellste Algorithmus für eine bereits geordnete Datei (genau N), aber in anderen Fällen ist er nicht effizient).

Antwort4

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

Andernfalls können Sie die Java-Bibliothek verwendenGroßsortierer. Es teilt die Eingabe in sortierte Zwischendateien auf und führt sie effizient zusammen (insgesamt O(nlogn)). Das Sortieren Ihrer Datei sieht folgendermaßen aus:

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

Ich habe eine 1,7 GB große Datei (100 Millionen Zeilen) mit zufällig generierten Wörtern mit jeweils 16 Zeichen erstellt und sie wie oben in 142 Sek. sortiert. Basierend auf der Rechenkomplexität von O(n log n) der von mir verwendeten Methode schätze ich, dass das Sortieren von 800 GB mit 16 Zeichen im Single-Thread-Verfahren auf meinem i5-Laptop mit 2,3 GHz und SSD etwa 24 Stunden dauern würde.

verwandte Informationen