Unix-Sortierung für teilweise geordnete Datensätze

Ich habe also eine enorm große Datei (ca. 10 GB) und muss sie sortieren, genau wie bei der Verwendung des Dienstprogramms "Sortieren", aber irgendwie effektiver.

Das Problem ist, dass ich keinen Speicher, keine CPU-Leistung, keine Zeit und keinen freien Austauschplatz habe, um die gesamte Sorte mit Strom zu versorgen.

Das Gute ist, dass die Datei bereits teilweise geordnet ist (ich kann sagen, dass der Abstand jeder Zeile von ihrer endgültigen Position kleiner als ein Wert N ist). Diese Art erinnert mich an das klassische Beispiel der Computerklasse für die Verwendung von Heapsort mit Heap der Größe N für diesen Zweck.

Frage: Gibt es ein Unix-Tool, das dies bereits effektiv erledigt, oder muss ich selbst eines codieren?

Danke -mk

Es wäre einfacher, die Datei in kleinere Abschnitte aufzuteilen und diese zu sortieren. Aufteilen:-

split --lines=100000 large_file file_part.

Sortieren Sie dann jede davon mit der normalen Sortierung

for suffix in `ls file_part.* | cut -f2 -d.` 
do 
  sort file_part.${suffix} > file_sorted.${suffix} 
done

Sie können dann durch Zusammenführungssortierung kombinieren

sort -m file_sorted.*

Das sollte auf Ihrer Maschine viel einfacher sein.

Sortieren, verwendet und R-Way-Merge-Sortieralgorithmus. Der schnellste Weg, um Ihre Arbeit zu erledigen, wäre:

sort myfile

Dies impliziert O (n logn) Zeitkomplexität und O (n) Zeit.

Wenn Sie die Daten partitionieren, werden Sie sie wahrscheinlich zeitlich bezahlen.

Der obige Code hat ein Problem. Mit sort -m wird nicht garantiert, dass die Dateien gegenseitig sortiert werden.

aus dem Unix-Handbuch:

   -m, --merge
          merge already sorted files; do not sort

z.B

file1: abcklq file2: dem

sort -m file1 file2 

abcklqdem

das ist nicht in der Art.

Auch die Tatsache, dass sich die Elemente an Stellen befinden, die kleiner als N sind, garantiert keine sortierte Ausgabe mit dem obigen Code:

Datei: aebcdhfg

in der Datei N = 3 und alle Elemente sind weniger als 3 Stellen als ihre richtige Stelle

Datei1: hfg, Datei2: bcd, Datei3: ae

sort file1

produziert:

Datei1: fgh, Datei2: bcd, Datei3: ae

und

sorm -m file3 file2 file1

Ausgänge:

aebcdfgh

was falsch ist.