¿Cómo podría ordenar el comando de clasificación UNIX un archivo muy grande?

Question

El comando UNIX sort puede ordenar un archivo muy grande como esto:

sort large_file 

cómo se implementa el algoritmo de ordenación?

¿Cómo es que no causa un consumo excesivo de memoria?

Answer 1

Algorithmic details of UNIX Sort command dice que Unix Sort utiliza un algoritmo de clasificación de combinación de R-Way externo. El enlace entra en más detalles, pero en esencia divide la entrada en porciones más pequeñas (que caben en la memoria) y luego fusiona cada porción al final.

Answer 2

El comando sort almacena datos de trabajo en archivos de disco temporales (generalmente en /tmp).

Answer 3

No estoy familiarizado con el programa, pero supongo que se hace mediante clasificación externa (la mayoría del problema se guarda en archivos temporales mientras que una parte relativamente pequeña del problema se almacena en la memoria a la vez). Ver Donald Knuth's The Art of Computer Programming, Vol. 3 Sorting and Searching, Section 5.4 para una discusión en profundidad del tema.

Answer 4

ADVERTENCIA: Este script inicia un shell por fragmento, para archivos realmente grandes, podrían ser cientos.

---

Aquí hay un script que escribí para este propósito. ¡En una máquina de 4 procesadores, mejoró el rendimiento de clasificación en un 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 

Consulte también: "Sorting large files faster with a shell script"

Answer 5

memoria no debería ser un problema - más o menos ya se encarga de eso. Si desea hacer un uso óptimo de su CPU multi-core, lo he implementado en un pequeño script (similar a algunos que podría encontrar en la red, pero más simple/más limpio que la mayoría de ellos;)).

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

prestar atención a la clase de opciones para acelerar el rendimiento y comprender su impacto en su máquina y problema. parámetros clave en Ubuntu son

• Ubicación de los archivos temporales -t directory_name
• cantidad de memoria para utilizar -SN% (N% de toda la memoria de usar, cuanto más mejor, pero evitar la sobre suscripción que provoca realizar intercambios con el disco. se puede utilizar como "-S 80%", para usar el 80% de RAM disponible, o "-S 2G" de 2 GB de RAM.)

El interlocutor pregunta "¿por qué no uso de memoria alta ? " La respuesta viene de la historia, las máquinas unix antiguas eran pequeñas y el tamaño de memoria predeterminado es pequeño. Ajuste esto lo más grande posible para su carga de trabajo para mejorar enormemente el rendimiento de clasificación. Establezca el directorio de trabajo en un lugar en su dispositivo más rápido que tenga espacio suficiente para contener al menos 1.25 * el tamaño del archivo que se está ordenando.