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

104

La sortcommande UNIX peut trier un très gros fichier comme ceci:

sort large_file

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

Comment se fait-il que cela ne cause pas une consommation excessive de mémoire?

yjfuk
la source
C'est intéressant. Je ne sais pas vraiment comment cela fonctionne, mais j'ai une supposition. Il met probablement le premier caractère de chaque clé dans un arbre binaire, et en cas de collision, il utilise également le caractère suivant de la clé, de sorte qu'il ne sauvegarde pas plus de clé qu'il n'en a besoin. Il peut ensuite enregistrer un décalage dans le fichier avec chaque touche afin de pouvoir rechercher et imprimer chaque ligne dans l'ordre.
Zifre
En fait, @ayaz est plus intéressant si vous ne triez pas un fichier sur disque mais plutôt dans un tube, car il est évident que vous ne pouvez pas simplement faire plusieurs passes sur les données d'entrée.
tvanfosson
3
Pourquoi tout le monde sur SO se sent-il si obligé de deviner tout le temps?
Vous pouvez effectuer plusieurs passes sur l'entrée - il vous suffit de lire toutes les entrées, de les écrire sur le disque, puis de trier le fichier du disque.
2
@Neil - du contexte, il semblait évident qu'il essayait de trier le contenu du fichier et non le nom du fichier (qui pour un nom n'a pas de sens). Je voulais juste améliorer la question sans trop changer le contexte pour qu'elle obtienne des réponses au lieu de votes négatifs à cause d'une simple erreur.
tvanfosson

Réponses:

111

Les détails algorithmiques de la commande UNIX Sort indiquent qu'Unix Sort utilise un algorithme de tri de fusion externe R-Way. Le lien entre dans plus de détails, mais en substance, il divise l'entrée en parties plus petites (qui s'insèrent dans la mémoire), puis fusionne chaque partie à la fin.

Matthieu
la source
42

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

user1686
la source
20
utiliser -Tpour spécifier le
répertoire
12

AVERTISSEMENT: ce script démarre un shell par bloc, pour les fichiers vraiment volumineux, cela peut être des centaines.


Voici un script que j'ai écrit à cet effet. Sur une machine à 4 processeurs, il a amélioré les performances de tri 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 des fichiers volumineux avec un script shell "

Adrian
la source
35
Vous pouvez simplement utiliser sort --parallel N à partir de la version GNU sort 8.11
jhclark
5
GNU coreutils 8.6 en fait
bdeonovic
1
Celui-ci a fait l'affaire pour moi. J'ai la version de la sorte 8.4. Utiliser le tri directement sur le fichier (190 millions de lignes) n'allait nulle part. Ce programme l'a fait en un peu moins de 4 minutes
Sunil B
encore une fois, cette réponse n'a rien à voir avec la question
WattsInABox
2
Ce script est dangereux. Ma machine Linux a perdu la réponse après avoir lancé des centaines de processus de tri…
Yongwei Wu
11

Je ne suis pas familier avec le programme, mais je suppose que cela se fait au moyen d'un tri externe (la plupart du problème est conservé dans des fichiers temporaires tandis qu'une partie relativement petite du problème est conservée en mémoire à la fois). Voir The Art of Computer Programming de Donald Knuth , Vol. 3 Tri et recherche, section 5.4 pour une discussion très approfondie du sujet.

pico
la source
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
la source
C'est excellent. Je ne savais pas qu'il y avait un paquet parallèle! Temps de tri amélioré de plus de 50% après avoir utilisé ce qui précède. Merci.
xbsd
J'ai essayé d'utiliser comm pour diff sur les fichiers générés par ceci et cela me prévient que les fichiers ne sont pas triés.
ashishb
7

Examinez attentivement les options de tri pour accélérer les performances et comprendre son impact sur votre machine et votre problème. Les paramètres clés sur Ubuntu sont

  • Emplacement des fichiers temporaires -T nom_répertoire
  • Quantité de mémoire à utiliser -SN% (N% de toute la mémoire à utiliser, plus il y en a, mieux c'est, mais évitez les surabonnements qui provoquent un échange sur disque. Vous pouvez l'utiliser comme "-S 80%" pour utiliser 80% de la RAM disponible, ou "-S 2G" pour 2 Go de RAM.)

Le questionneur demande "Pourquoi pas d'utilisation élevée de la mémoire?" La réponse à cela vient de l'histoire, les anciennes machines Unix étaient petites et la taille de la mémoire par défaut est réduite. Ajustez cela aussi grand que possible pour votre charge de travail afin d'améliorer considérablement les performances de tri. Définissez le répertoire de travail sur un emplacement de votre appareil le plus rapide disposant de suffisamment d'espace pour contenir au moins 1,25 * la taille du fichier en cours de tri.

Fred Gannett
la source
essayer ceci sur un fichier de 2,5 Go, sur une boîte avec 64 Go de RAM avec -S 80%, il utilise en fait ce pourcentage complet, même si le fichier entier est plus petit que cela. pourquoi donc? même s'il n'utilise pas de tri sur place qui semble gratuit
Joseph Garvin
Il est probable que sort -S pré-alloue la mémoire pour le processus de tri avant même de lire le contenu du fichier.
Fred Gannett
-3

La mémoire ne devrait pas être un problème - le tri s'en charge déjà. Si vous voulez utiliser de manière optimale votre processeur multicœur, je l'ai implémenté dans un petit script (similaire à certains que vous pourriez trouver sur le net, mais plus simple / plus propre que la plupart de ceux-ci;)).

#!/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.
la source
4
Script intéressant, mais il ne répond en rien à cette question.
Joachim Sauer le
5
split -b sera divisé par octets, tronquant ainsi les lignes à une position arbitraire
ithkuil