In che modo il comando di ordinamento UNIX può ordinare un file molto grande?

Question

Il comando UNIX sort possibile ordinare un file molto grande in questo modo:

sort large_file 

Come è l'algoritmo di ordinamento attuata?

Come mai non causa un consumo eccessivo di memoria?

Answer 1

Algorithmic details of UNIX Sort command dice che Unix Sort utilizza un algoritmo di ordinamento di fusione merker R-Way esterno. Il collegamento entra in maggiori dettagli, ma in sostanza divide l'input in porzioni più piccole (che si adattano alla memoria) e quindi unisce ciascuna porzione alla fine.

Answer 2

Il comando sort memorizza i dati di lavoro nei file del disco temporanei (in genere in /tmp).

Answer 3

Non ho dimestichezza con il programma, ma suppongo che sia fatto per mezzo di un ordinamento esterno (la maggior parte del problema è contenuta in file temporanei mentre una parte relativamente piccola del problema è conservata in memoria alla volta). Vedi Donald Knuth's The Art of Computer Programming, Vol. 3 Sorting and Searching, Section 5.4 per una discussione molto approfondita sull'argomento.

Answer 4

ATTENZIONE: Questo script avvia una shell per blocco, per file molto grandi, potrebbe essere centinaia.

---

Ecco uno script che ho scritto per questo scopo. Su una macchina a 4 processori ha migliorato le prestazioni di ordinamento del 100%!

#! /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 

Consulta anche: "Sorting large files faster with a shell script"

Answer 5

memoria non dovrebbe essere un problema - sorta già si occupa di questo. Se vuoi fare un uso ottimale della tua CPU multi-core, lo ho implementato in un piccolo script (simile ad alcuni che potresti trovare in rete, ma più semplice/più pulito della maggior parte di quelli;)).

#!/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* 

Answer 6

#!/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 

Answer 7

Guardate attentamente le opzioni di sorta per velocizzare le prestazioni e capire il suo impatto sulla vostra macchina e di problem. parametri chiave su Ubuntu sono

• posizione dei file temporanei -t directory_name
• quantità di memoria da utilizzare -SN% (N% di tutta la memoria da utilizzare, più sono e meglio, ma evitare un eccesso di sottoscrizione che provoca è possibile utilizzarlo come "-S 80%" per utilizzare l'80% della RAM disponibile o "-S 2G" per 2 GB di RAM.)

L'interrogante chiede "Perché non utilizza memoria elevata ?" La risposta a questo viene dalla cronologia, le macchine unix precedenti erano piccole e la dimensione della memoria predefinita è ridotta. Regola il più grande possibile per il tuo carico di lavoro per migliorare notevolmente le prestazioni di ordinamento. Imposta la directory di lavoro in un punto del tuo dispositivo più veloce che abbia spazio sufficiente per contenere almeno 1,25 * la dimensione del file che viene ordinato.