Algorithme de tri externe

Le tri fusion externe divise l'entrée en blocs de taille à tenir dans la mémoire principale, puis fusionne les différents blocs triés[1] - [2].

Supposons que nous souhaitons trier 9Gb de données en ne disposant que de 1Gb de mémoire vive. L'idée de l'algorithme est la suivante :

1. Charger 1Gb de données en mémoire vive et le trier en utilisant un algorithme de tri classique.
2. Écrire ces données triées dans un fichier disque temporaire.
3. Répéter les deux premières étapes pour le reste des données. L'entrée est de taille 9Gb, nous disposons donc de 9 fichiers triés de 1Gb chacun, que l'on cherche désormais à fusionner.
4. Copier en mémoire les premiers 100Mb (=0,1Gb) de chaque fichier trié. Chaque zone de 100Mb peut être vue comme un tampon d'entrée. Il reste sur la mémoire vive 1Gb-9*100Mb=100Mb libres, que nous utilisons comme tampon de sortie.
5. Fusionner petit à petit les 9 entrées, et écrire le résultat sur le tampon de sortie. Lorsqu'un tampon d'entrée se vide, les 100Mb suivants du fichier correspondant y sont chargés. Lorsque le tampon de sortie est plein, son contenu est écrit sur le disque (il s'agit de la sortie finale de l'algorithme).

L'idée clé de l'algorithme réside dans l'étape 5. Puisque les fichiers de taille 1Gb ont été triés, il n'est pas nécessaire pour les fusionner de les lire simultanément en intégralité : la plus petite valeur de l'ensemble d'entrée est nécessairement la plus petite (donc première) valeur d'un des neuf fichiers temporaires.

Notons que tous les fichiers temporaires créés sont fusionnés lors d'une unique fusion. Si cette technique peut se révéler optimale dans certains cas, elle n'est le plus souvent pas viable. En effet, pour une quantité de mémoire vive fixée, plus la taille de l'entrée est grande, et plus le nombre de fichiers temporaires créés est important. Lors de la fusion, la mémoire vive est divisée en autant de tampons et ceux-ci perdent toute leur utilité, le plus gros du temps étant alors passé à copier des données entre les mémoires principale et externe. De plus, la décision de diviser la mémoire vive en 10 tampons est totalement arbitraire ; d'autres valeurs pourraient être utilisées.

L'exemple ci-dessus pourrait être désigné comme un algorithme de tri fusion externe à deux passages. Le premier passage consiste en le tri des neuf fichiers de 1Gb, et le second passage en leur fusion. Une manière de résoudre les difficultés évoquées est d'effectuer une fusion en plusieurs passages.

Notons ${\displaystyle P}$ le nombre de passages, ${\displaystyle T}$ le nombre de tampons (entrées + sorties), chacun étant de taille ${\displaystyle S}$, et ${\displaystyle N}$ la taille de l'entrée. Dans le cas d'exemple, nous avions un passage de tri et un passage de fusion, utilisant neuf tampons d'entrée et un de sortie, soit ${\displaystyle P=2}$, ${\displaystyle T=10}$, ${\displaystyle S=100{\text{Mb}}}$ et ${\displaystyle N=9{\text{Gb}}}$. Lors de chaque passage de fusion, les fichiers temporaires produits lors du passage précédent sont fusionnés par groupes de ${\displaystyle T-1}$ et le résultat est écrit dans un nouveau fichier temporaire. Le nombre de fichiers temporaires réduit à chaque passage, et le dernier passage fusionne ${\displaystyle T-1}$ fichiers ou moins en un unique fichier qui correspond à la sortie de l'algorithme.

Lors du premier passage, les données sont triées par blocs de taille ${\displaystyle T\cdot S}$ ; la notion de tampon n'est pas importante dans ce cas, ${\displaystyle T\cdot S}$ correspondant à la taille totale de la mémoire principale disponible, qui est à ce moment utilisée comme elle le serait pour n'importe quel algorithme de tri classique. Le nombre de fichiers temporaires créés est donc ${\displaystyle \lceil N/(T\cdot S)\rceil }$. À chaque passage suivant, nous effectuons des fusions à ${\displaystyle T-1}$ entrées. Le nombre de passages nécessaires est donc donné par la relation :

${\displaystyle P=1+\left\lceil \log _{T-1}\left\lceil {\frac {N}{T\cdot S}}\right\rceil \right\rceil }$

Lors de chaque fusion, on effectue ${\displaystyle 2N/S}$ lectures ou écritures sur le disque. La complexité totale est donc donnée par :

${\displaystyle C=2{\frac {N}{S}}\left(1+\left\lceil \log _{T-1}\left\lceil {\frac {N}{T\cdot S}}\right\rceil \right\rceil \right)}$

Lors d'une fusion à plus de deux entrées, il est nécessaire à chaque itération de comparer toutes les différentes entrées entre elles. Pour éviter d'effectuer un nombre trop grand de comparaisons, une solution est d'utiliser un arbre de sélection[3], c'est-à-dire un arbre binaire dont chaque nœud interne est étiqueté (dans notre cas) par la valeur du plus petit de ses fils. Les feuilles de l'arbre correspondent aux ${\displaystyle T-1}$ plus petits éléments de chaque entrée à comparer entre eux. L'insertion d'une nouvelle valeur, qui correspond à une simple mise à jour de l'arbre, s'effectue en ${\displaystyle \lceil \log _{2}(T-1)\rceil }$ comparaisons.

Jim Gray a créé un comparatif d'algorithmes de tri externes finement paramétrés et optimisés. Plusieurs techniques sont utilisées pour réduire le temps d'exécution.

• Utilisation du parallélisme.
  • Plusieurs disques durs peuvent être utilisés en parallèle pour augmenter la vitesse totale de lecture et d'écriture.
  • Plusieurs threads peuvent être utilisés pour exploiter les possibilités des microprocesseurs multi-cœurs.
  • Les programmes peuvent effectuer des entrées/sorties asynchrones, de telle sorte qu'une partie des données peut être fusionnée tandis que d'autres données sont lues ou écrites sur disque.
  • Il est possible d'utiliser une grappe d'ordinateurs mis en réseau. TritonSort[4] a par exemple été testé sur une grappe de 52 machines pour trier 100Tb de données.
• Réduire la durée des entrées/sorties.
  • Utiliser plus de mémoire vive permet de limiter le nombre de passages.
  • Les temps d'accès peuvent être réduis en utilisant de la mémoire externe rapide, comme la technologie SSD, que ce soit en intégralité ou de manière hybride avec des disques durs.
• Autres optimisations.
  • Certains tris utilisent une variante du tri par base lors du premier passage : ils séparent les données en sous-ensembles en fonction du commencement des valeurs (c.f. tri par distribution).
  • S'il s'agit de trier des données longues en utilisant des clés courtes, il est possible de réarranger les clés séparément des valeurs afin de réduire la taille des entrées/sorties.

Dans les débuts de l'informatique, lorsque le coût des mémoires de type disques ou tambours magnétiques était très élevé, les algorithmes de tri pouvaient n'utiliser que la mémoire centrale et les dérouleurs de bandes magnétiques.

En l'absence de disque, il fallait au moins quatre dérouleurs de bandes pour pratiquer un tel tri. Avec 4 dérouleurs (b1, b2, b3, b4), les opérations étaient les suivantes :

1. montage (manuel) du fichier à trier sur le dérouleur b1, et de bandes de manœuvre sur b2, b3, b4 ;
2. lecture de b1 par paquets successifs qui sont triés en mémoire, pour générer des monotonies qui sont écrites en alternance sur les dérouleurs b3 et b4 ;
3. sur le dérouleur b1, démontage de la bande contenant le fichier initial pour le remplacer par une bande de manœuvre ;
4. fusion (interclassement) des bandes b3 et b4 pour générer en alternance sur b1 et b2 des monotonies dont le volume est doublé ;
5. fusion de b1 et b2 sur b3 b4, et itération de (4) et (5) jusqu'à ce que les monotonies atteignent 50 % du volume à trier ;
6. fusion finale pour générer le résultat.

En pratique, compte tenu de la fiabilité moyenne des équipements, on rencontrait donc fréquemment des salles machines avec huit dérouleurs de bandes.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « External sorting » (voir la liste des auteurs).

• Variantes du tri fusion externe, choix des paramètres optimaux et arbres de sélection
• (en) Coût du tri fusion externe et variantes
• (en) Présentation de plusieurs variantes du tri fusion externe
• (en) Comparatif des algorithmes de tri externe optimisés

• (en) STXXL, une bibliothèque pour données de grandes tailles incluant un tri externe
• (en) Implémentation en C++
• (en) Implémentation de la fusion à k entrée avec un arbre de sélection
• (en) Implémentation d'un tri externe en Java