Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme de tri externe
Résumé
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.
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.
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 :
Charger 1Gb 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 9Gb, nous disposons donc de 9 fichiers triés de 1Gb chacun, que l'on cherche désormais à fusionner.
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.
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.