Algorithme de tri externe

Un algorithme de tri est dit externe lorsqu'il permet de trier des entrées trop grandes pour être contenues en intégralité dans la mémoire principale d'un ordinateur. En règle générale, la mémoire principale est la mémoire vive, et l'algorithme recourt donc à l'usage d'une mémoire située plus bas dans la hiérarchie mémoire, comme un disque dur.

Recourir à la mémoire externe permet d'arriver à trier des volumes de données plus importants mais induit de nouvelles difficultés, le temps d'accès aux données étant beaucoup plus long. Aller chercher chaque valeur sur le disque lorsque l'on en a besoin serait trop lent ; en pratique, les approches qui fonctionnent travaillent successivement sur différentes parties des données chargées temporairement dans la mémoire principale. Les algorithmes de tri externe sont donc typiquement des variantes du tri fusion, qui s'adapte bien à ces contraintes : l'entrée est divisée en sous-ensembles pouvant être chargés un à un en mémoire, triés puis réécrits dans des fichiers temporaires qui sont ensuite fusionnés.

Tri fusion modifier

Idée de l'algorithme modifier

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 9 Gb de données en ne disposant que de 1 Gb de mémoire vive. L'idée de l'algorithme est la suivante :

Charger 1 Gb de données en mémoire vive et le trier en utilisant un algorithme de tri classique.
Écrire ces données triées dans un fichier disque temporaire.
Répéter les deux premières étapes pour le reste des données. L'entrée est de taille 9 Gb, nous disposons donc de 9 fichiers triés de 1 Gb chacun, que l'on cherche désormais à fusionner.
Copier en mémoire les premiers 100 Mb (=0,1 Gb) de chaque fichier trié. Chaque zone de 100 Mb peut être vue comme un tampon d'entrée. Il reste sur la mémoire vive 1 Gb - 9*100 Mb=100 Mb libres, que nous utilisons comme tampon de sortie.
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 100 Mb 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 1 Gb 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.

Généralisation modifier

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 1 Gb, 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 $P$ le nombre de passages, $T$ le nombre de tampons (entrées + sorties), chacun étant de taille $S$ , et $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 $P=2$ , $T=10$ , $S=100{\text{Mb}}$ et $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 $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 $T-1$ fichiers ou moins en un unique fichier qui correspond à la sortie de l'algorithme.

Étude de la complexité modifier

Lors du premier passage, les données sont triées par blocs de taille $T\cdot S$ ; la notion de tampon n'est pas importante dans ce cas, $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 $\lceil N/(T\cdot S)\rceil$ . À chaque passage suivant, nous effectuons des fusions à $T-1$ entrées. Le nombre de passages nécessaires est donc donné par la relation :

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

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

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

Fusion modifier

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 $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 $\lceil \log _{2}(T-1)\rceil$ comparaisons.

Implémentations optimisées modifier

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 100 Tb 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éduits 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.

Tris bande modifier

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 :

montage (manuel) du fichier à trier sur le dérouleur b1, et de bandes de manœuvre sur b2, b3, b4 ;
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 ;
sur le dérouleur b1, démontage de la bande contenant le fichier initial pour le remplacer par une bande de manœuvre ;
fusion (interclassement) des bandes b3 et b4 pour générer en alternance sur b1 et b2 des monotonies dont le volume est doublé ;
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 ;
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.

Tri par distribution modifier

Les tris par distribution distribuent les entrées en sous-ensembles de plus petites tailles en fonction de leurs valeurs (typiquement, on effectue une partition de l'ensemble des éléments à trier). Ils s'adaptent également à l'utilisation de mémoire externe, les sous-ensembles pouvant être écrits en différents fichiers. La principale difficulté de ces algorithmes est de trouver la partition utilisée pour la distribution^[5].

Annexes modifier

Notes et références modifier

↑ (en) Donald Knuth, The Art of Computer Programming : Sorting and searching, vol. Volume 3: Sorting and Searching, Addison-Wesley, 1998, 2^e éd., 780 p. (ISBN 978-0-201-89685-5), p. 248–379
↑ (en) Ellis Horowitz et Sartaj Sahni, Fundamentals of Data Structures, H. Freeman & Co. (ISBN 978-0-7167-8042-7)
↑ « Les méthodes de tri externe »
↑ (en) Rasmussen, Alexander, Porter, George, Conley, Michael, Madhyastha, Harsha V, Mysore, Radhika Niranjan, Pucher, Alexander et Vahdat, Amin, « TritonSort: A Balanced Large-Scale Sorting System. », NSDI,‎ 2011 (lire en ligne)
↑ (en) J. S. Vitter, Algorithms and Data Structures for External Memory, now Publishers, 2008, 174 p. (ISBN 978-1-60198-106-6, lire en ligne), p. 31-38

(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).

Liens externes modifier

Théorie modifier

Implémentations modifier

Portail de l'informatique théorique

[1] (en) Donald Knuth, The Art of Computer Programming : Sorting and searching, vol. Volume 3: Sorting and Searching, Addison-Wesley, 1998, 2^e éd., 780 p. (ISBN 978-0-201-89685-5), p. 248–379

[2] (en) Ellis Horowitz et Sartaj Sahni, Fundamentals of Data Structures, H. Freeman & Co. (ISBN 978-0-7167-8042-7)

[3] « Les méthodes de tri externe »

[4] (en) Rasmussen, Alexander, Porter, George, Conley, Michael, Madhyastha, Harsha V, Mysore, Radhika Niranjan, Pucher, Alexander et Vahdat, Amin, « TritonSort: A Balanced Large-Scale Sorting System. », NSDI,‎ 2011 (lire en ligne)

[5] (en) J. S. Vitter, Algorithms and Data Structures for External Memory, now Publishers, 2008, 174 p. (ISBN 978-1-60198-106-6, lire en ligne), p. 31-38

[1]

[2]

[3]

[4]

[5]