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.
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 lineif[ $# != 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
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.
#!/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 lineif[ $# != 2 ]then
usage
exit
fi
pv $1 | parallel --pipe --files sort -S512M | parallel -Xj1 sort -S1024M -m {}';' rm {}> $2
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.
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=0for 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*
Réponses:
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.
la source
La
sort
commande stocke les données de travail dans des fichiers de disque temporaires (généralement dans/tmp
).la source
-T
pour spécifier leAVERTISSEMENT: 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%!
Voir aussi: " Tri plus rapide des fichiers volumineux avec un script shell "
la source
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.
la source
la source
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
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.
la source
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;)).
la source