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

El sortcomando UNIX puede ordenar un archivo muy grande como este:

sort large_file

¿Cómo se implementa el algoritmo de clasificación?

¿Por qué no provoca un consumo excesivo de memoria?

Los detalles algorítmicos del comando UNIX Sort indican que Unix Sort usa un algoritmo de clasificación de fusión R-Way externo. El enlace entra en más detalles, pero en esencia divide la entrada en porciones más pequeñas (que encajan en la memoria) y luego fusiona cada porción al final.

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

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

Aquí hay un guión 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: " Ordenar archivos grandes más rápido con un script de shell "

No estoy familiarizado con el programa, pero supongo que se realiza mediante una clasificación externa (la mayor parte del problema se mantiene en archivos temporales, mientras que una parte relativamente pequeña del problema se mantiene en la memoria a la vez). Véase El arte de la programación informática de Donald Knuth , vol. 3 Clasificación y búsqueda, Sección 5.4 para una discusión más profunda del tema.

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

Observe detenidamente las opciones de clasificación para acelerar el rendimiento y comprenda su impacto en su máquina y su problema. Los parámetros clave en Ubuntu son

• Ubicación de los archivos temporales -T nombre_directorio
• Cantidad de memoria para usar -SN% (N% de toda la memoria para usar, cuanto más, mejor, pero evite la suscripción excesiva que causa el intercambio al disco. Puede usarlo como "-S 80%" para usar el 80% de la RAM disponible, o "-S 2G" para 2 GB de RAM).

El interrogador pregunta "¿Por qué no hay un uso elevado de memoria?" La respuesta a eso viene de la historia, las máquinas Unix más antiguas eran pequeñas y el tamaño de memoria predeterminado es pequeño. Ajústelo lo más grande posible para su carga de trabajo para mejorar enormemente el rendimiento de clasificación. Configure el directorio de trabajo en un lugar de su dispositivo más rápido que tenga suficiente espacio para contener al menos 1,25 * el tamaño del archivo que se está ordenando.

La memoria no debería ser un problema, sort ya se encarga de eso. Si desea hacer un uso óptimo de su CPU de múltiples núcleos, he implementado esto en un pequeño script (similar a algunos que puede encontrar en la red, pero más simple / más limpio que la mayoría de esos;)).

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