Das ist interessant. Ich weiß nicht wirklich, wie es funktioniert, aber ich habe eine Vermutung. Wahrscheinlich wird das erste Zeichen jedes Schlüssels in einen Binärbaum eingefügt, und bei einer Kollision wird auch das nächste Zeichen des Schlüssels verwendet, sodass nicht mehr vom Schlüssel gespeichert wird, als benötigt wird. Anschließend kann mit jedem Schlüssel ein Versatz in der Datei gespeichert werden, sodass jede Zeile der Reihe nach gesucht und gedruckt werden kann.
Zifre
Tatsächlich ist @ayaz interessanter, wenn Sie eine Datei nicht auf der Festplatte, sondern in einer Pipe sortieren, da dies offensichtlich macht, dass Sie nicht einfach mehrere Durchgänge über die Eingabedaten durchführen können.
Tvanfosson
3
Warum fühlen sich alle auf SO so gezwungen, die ganze Zeit zu raten?
Sie können die Eingabe mehrfach durchlaufen - Sie müssen nur die gesamte Eingabe lesen, auf die Festplatte schreiben und dann die Festplattendatei sortieren.
2
@Neil - aus dem Kontext schien es offensichtlich, dass er versuchte, den Inhalt der Datei zu sortieren, nicht den Dateinamen (was für einen Namen bedeutungslos ist). Ich wollte die Frage nur verbessern, ohne den Kontext zu stark zu ändern, damit sie aufgrund eines einfachen Fehlers Antworten anstelle von Abstimmungen erhält.
Tvanfosson
Antworten:
111
Die algorithmischen Details des UNIX -Sortierbefehls besagen, dass Unix Sort einen externen R-Way-Merge-Sortieralgorithmus verwendet. Der Link geht auf weitere Details ein, teilt die Eingabe jedoch im Wesentlichen in kleinere Teile (die in den Speicher passen) auf und führt dann jeden Teil am Ende zusammen.
WARNUNG: Dieses Skript startet eine Shell pro Block. Bei sehr großen Dateien können dies Hunderte sein.
Hier ist ein Skript, das ich zu diesem Zweck geschrieben habe. Auf einem 4-Prozessor-Computer wurde die Sortierleistung um 100% verbessert!
#! /bin/ksh
MAX_LINES_PER_CHUNK=1000000
ORIGINAL_FILE=$1
SORTED_FILE=$2
CHUNK_FILE_PREFIX=$ORIGINAL_FILE.split.
SORTED_CHUNK_FILES=$CHUNK_FILE_PREFIX*.sorted
usage (){
echo Parallel sort
echo usage: psort file1 file2
echo Sorts text file file1 and stores the output in file2
echo Note: file1 will be split in chunks up to $MAX_LINES_PER_CHUNK lines
echo and each chunk will be sorted in parallel
}# test if we have two arguments on the command lineif[ $# != 2 ]then
usage
exit
fi#Cleanup any lefover files
rm -f $SORTED_CHUNK_FILES >/dev/null
rm -f $CHUNK_FILE_PREFIX*>/dev/null
rm -f $SORTED_FILE
#Splitting $ORIGINAL_FILE into chunks ...
split -l $MAX_LINES_PER_CHUNK $ORIGINAL_FILE $CHUNK_FILE_PREFIX
for file in $CHUNK_FILE_PREFIX*do
sort $file > $file.sorted &done
wait
#Merging chunks to $SORTED_FILE ...
sort -m $SORTED_CHUNK_FILES > $SORTED_FILE
#Cleanup any lefover files
rm -f $SORTED_CHUNK_FILES >/dev/null
rm -f $CHUNK_FILE_PREFIX*>/dev/null
Sie können einfach sort --parallel N ab GNU sort version 8.11
jhclark
5
GNU Coreutils 8.6 tatsächlich
Bdeonovic
1
Dieser hat den Trick für mich getan. Ich habe die Version 8.4. Die Verwendung von sort direkt in der Datei (190 Millionen Zeilen) ging nirgendwo hin. Dieses Programm hat es mit knapp 4 Minuten geschafft
Sunil B
Auch diese Antwort hat nichts mit der Frage zu tun
WattsInABox
2
Dieses Skript ist gefährlich. Mein Linux-Computer verlor die Antwort, nachdem er Hunderte von Sortierprozessen
gestartet hatte
11
Ich bin mit dem Programm nicht vertraut, aber ich denke, es wird durch externe Sortierung durchgeführt (der größte Teil des Problems wird in temporären Dateien gespeichert, während ein relativ kleiner Teil des Problems gleichzeitig im Speicher gespeichert wird). Siehe Donald Knuths The Art of Computer Programming, Vol. 3, No. 3 Sortieren und Suchen, Abschnitt 5.4 für eine sehr eingehende Diskussion des Themas.
#!/bin/bash
usage (){
echo Parallel sort
echo usage: psort file1 file2
echo Sorts text file file1 and stores the output in file2
}# test if we have two arguments on the command lineif[ $# != 2 ]then
usage
exit
fi
pv $1 | parallel --pipe --files sort -S512M | parallel -Xj1 sort -S1024M -m {}';' rm {}> $2
Das ist ausgezeichnet. Wusste nicht, dass es ein Parallelpaket gab! Die Sortierzeit verbesserte sich nach Verwendung der oben genannten um mehr als 50%. Vielen Dank.
XBSD
Ich habe versucht, comm für diff für die von diesem generierten Dateien zu verwenden, und es warnt mich, dass Dateien nicht sortiert sind.
Ashishb
7
Schauen Sie sich die Sortieroptionen genau an, um die Leistung zu beschleunigen, und verstehen Sie die Auswirkungen auf Ihre Maschine und Ihr Problem. Wichtige Parameter unter Ubuntu sind
Speicherort der temporären Dateien -T Verzeichnisname
Zu verwendende Speichermenge -SN% (N% des gesamten zu verwendenden Speichers, je mehr desto besser, aber vermeiden Sie ein Überabonnement, das zu einem Austausch auf die Festplatte führt. Sie können es wie "-S 80%" verwenden, um 80% des verfügbaren Arbeitsspeichers zu verwenden. oder "-S 2G" für 2 GB RAM.)
Der Fragesteller fragt: "Warum keine hohe Speichernutzung?" Die Antwort darauf stammt aus der Geschichte, ältere Unix-Maschinen waren klein und die Standardspeichergröße ist klein eingestellt. Passen Sie dies so groß wie möglich an, damit Ihre Arbeitslast die Sortierleistung erheblich verbessert. Stellen Sie das Arbeitsverzeichnis auf einen Ort auf Ihrem schnellsten Gerät ein, der über genügend Speicherplatz für mindestens 1,25 * der Größe der zu sortierenden Datei verfügt.
Wenn Sie dies an einer 2,5-GB-Datei und an einer Box mit 64 GB RAM mit -S 80% ausprobieren, wird tatsächlich dieser volle Prozentsatz verwendet, obwohl die gesamte Datei kleiner ist. warum ist das so? auch wenn es keine In-Place-Sorte verwendet, die unentgeltlich erscheint
Joseph Garvin
Wahrscheinlich ordnet sort -S den Speicher für den Sortiervorgang vorab zu, bevor überhaupt der Inhalt der Datei gelesen wird.
Fred Gannett
-3
Der Speicher sollte kein Problem sein - die Sortierung kümmert sich bereits darum. Wenn Sie Ihre Multi-Core-CPU optimal nutzen möchten, habe ich dies in einem kleinen Skript implementiert (ähnlich wie einige, die Sie im Internet finden, aber einfacher / sauberer als die meisten anderen;)).
#!/bin/bash# Usage: psort filename <chunksize> <threads># In this example a the file largefile is split into chunks of 20 MB.# The part are sorted in 4 simultaneous threads before getting merged.# # psort largefile.txt 20m 4 ## by h.p.
split -b $2 $1 $1.part
suffix=sorttemp.`date +%s`
nthreads=$3
i=0for fname in`ls *$1.part*`do
let i++
sort $fname > $fname.$suffix &
mres=$(($i % $nthreads))
test "$mres"-eq 0&& wait
done
wait
sort -m *.$suffix
rm $1.part*
Antworten:
Die algorithmischen Details des UNIX -Sortierbefehls besagen, dass Unix Sort einen externen R-Way-Merge-Sortieralgorithmus verwendet. Der Link geht auf weitere Details ein, teilt die Eingabe jedoch im Wesentlichen in kleinere Teile (die in den Speicher passen) auf und führt dann jeden Teil am Ende zusammen.
quelle
Der
sort
Befehl speichert Arbeitsdaten in temporären Datenträgerdateien (normalerweise in/tmp
).quelle
-T
, um die Temperatur dirWARNUNG: Dieses Skript startet eine Shell pro Block. Bei sehr großen Dateien können dies Hunderte sein.
Hier ist ein Skript, das ich zu diesem Zweck geschrieben habe. Auf einem 4-Prozessor-Computer wurde die Sortierleistung um 100% verbessert!
Siehe auch: " Große Dateien mit einem Shell-Skript schneller sortieren "
quelle
Ich bin mit dem Programm nicht vertraut, aber ich denke, es wird durch externe Sortierung durchgeführt (der größte Teil des Problems wird in temporären Dateien gespeichert, während ein relativ kleiner Teil des Problems gleichzeitig im Speicher gespeichert wird). Siehe Donald Knuths The Art of Computer Programming, Vol. 3, No. 3 Sortieren und Suchen, Abschnitt 5.4 für eine sehr eingehende Diskussion des Themas.
quelle
quelle
Schauen Sie sich die Sortieroptionen genau an, um die Leistung zu beschleunigen, und verstehen Sie die Auswirkungen auf Ihre Maschine und Ihr Problem. Wichtige Parameter unter Ubuntu sind
Der Fragesteller fragt: "Warum keine hohe Speichernutzung?" Die Antwort darauf stammt aus der Geschichte, ältere Unix-Maschinen waren klein und die Standardspeichergröße ist klein eingestellt. Passen Sie dies so groß wie möglich an, damit Ihre Arbeitslast die Sortierleistung erheblich verbessert. Stellen Sie das Arbeitsverzeichnis auf einen Ort auf Ihrem schnellsten Gerät ein, der über genügend Speicherplatz für mindestens 1,25 * der Größe der zu sortierenden Datei verfügt.
quelle
Der Speicher sollte kein Problem sein - die Sortierung kümmert sich bereits darum. Wenn Sie Ihre Multi-Core-CPU optimal nutzen möchten, habe ich dies in einem kleinen Skript implementiert (ähnlich wie einige, die Sie im Internet finden, aber einfacher / sauberer als die meisten anderen;)).
quelle