Exercice tri externe
Question
Supposons qu'on souhaite trier un fichier de 75 000 pages de 4 Ko (soit une taille totale de 307 Mo). Donnez le nombre de lectures et d'écritures (en terme de pages de 4Ko) lorsqu'on dispose d'une mémoire de 307Mo. Idem lorsqu'on dispose d'une mémoire de 2 Mo, puis de 1Mo.
Solution
RAM = 307Mo
Il faut lire l'ensemble des 75 000 pages, puis trier le tout en mémoire (puisqu'on a suffisamment de place), puis écrire le résultat (75 000 pages).
Bilan : 75 000 lectures, et 75 000 écritures
Solution
RAM = 2Mo
on lit et on trie les 75 000 pages
on effectue un tri fusion, sachant qu'on peut garder en mémoire 2048/4 =512 pages, et donc on peut les fusionner 256 par 256. Le nombre de paquets à fusionner au premier niveau est donc 75 000 / 256 = 293, et le nombre de niveaux est donc l'arrondi à l'entier supérieur de log2(293) soit 9. On lira et écrire donc 9 fois l'ensemble de données, en plus de la lecture initiale.
Le coût total est donc de 750 000 lectures et 750 000 écritures !
Solution
RAM = 1Mo
On fait le même calcul sachant qu'on peut garder en mémoire 256 pages, donc on ne peut les fusionner que 128 par 128 et donc qu'on a 586 paquets initiaux, et qu'on devra donc effectuer 10 rounds.
Le coût total est donc de 825 000 lectures et 825 000 écritures.