Wie kann der UNIX-Sortierbefehl eine sehr große Datei sortieren?

104

Der UNIX- sortBefehl kann eine sehr große Datei wie folgt sortieren:

sort large_file

Wie ist der Sortieralgorithmus implementiert?

Wie kommt es, dass es keinen übermäßigen Speicherverbrauch verursacht?

yjfuk
quelle
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.

Matthew
quelle
42

Der sortBefehl speichert Arbeitsdaten in temporären Datenträgerdateien (normalerweise in /tmp).

user1686
quelle
20
Verwenden Sie -T, um die Temperatur dir
glenn jackman
12

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 line
if [ $# != 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

Siehe auch: " Große Dateien mit einem Shell-Skript schneller sortieren "

Adrian
quelle
35
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.

Pico
quelle
11
#!/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 line
if [ $# != 2 ]
then
    usage
    exit
fi

pv $1 | parallel --pipe --files sort -S512M | parallel -Xj1 sort -S1024M -m {} ';' rm {} > $2
Sergio
quelle
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.

Fred Gannett
quelle
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=0
for 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*
hannes.p.
quelle
4
Interessantes Skript, aber es tut nichts, um diese Frage zu beantworten.
Joachim Sauer
5
split -b wird durch Bytes geteilt, wodurch die Zeilen an einer beliebigen Position
abgeschnitten werden