Comment la commande de tri UNIX peut-elle trier un très gros fichier?

Question

La commande UNIX sort peut trier un très gros fichier comme suit:

 sort large_file
 

Comment l'algorithme de tri est-il implémenté?

Comment se fait-il qu'il ne provoque pas une consommation excessive de mémoire?

Answer 1

La commande Algorithmic details of UNIX Sort indique que la commande Unix Sort utilise un algorithme de tri de fusion R-Way externe. Le lien entre dans plus de détails, mais il divise essentiellement l’entrée en parties plus petites (qui entrent dans la mémoire), puis fusionne chaque partie à la fin.

Answer 2

La commande sort stocke les données de travail dans des fichiers de disque temporaires (généralement sous forme de /tmp ).

Answer 3

Voici un script que j'ai écrit à cet effet. Sur une machine à 4 processeurs, les performances de tri ont été améliorées de 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
 

Voir aussi: " Tri plus rapide de gros fichiers avec un script shell "

Answer 4

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

Je ne connais pas bien le programme, mais j'imagine que cela se fait au moyen d'un tri externe (la plupart des problèmes sont conservés dans des fichiers temporaires, tandis qu'une partie relativement petite du problème est conservée en mémoire à la fois). Voir L'art de la programmation informatique de Donald Knuth , vol. 3 Tri et recherche, section 5.4 pour une discussion très approfondie du sujet.