Quelques Algorithmes de Tri

Il existe beaucoup d'algorithmes de tri mai en cours nous n'en étudions qu'un sous-ensemble très limité. En général, il s'agit des quelques tris itératifs (sélection, insertion, bulle) et récursifs (fusion et rapide). La complexité de ces tris est très facile à calculer et en les implémentant, on peut la vérifier expérimentalement.

Implémentation Java

L'implémentation Java est assez simple et ne fait pas appel à des concepts avancés. Pour des raisons de simplification, la classe qui contient les tris (Main.java) ne contient que des méthodes statiques. Afin de stocker le résultat des expérimentations, nous utilisons un objet (ResultatsExperiences.java) qui permet de stocker le nom du tri, la taille des données et le temps mesuré. Cela nous permet ensuite d'afficher l'ensemble des résultats pour les importer dans un tableur. Les deux fichiers peuvent être téléchargés en bas de la page.

Protocole Expérimental

Chaque tri est testé avec un tableau aléatoire, généré avant chaque expérience. La taille du tableau varie de i à 10*i pour chacun des tris. Un tour de chauffe est effectué avant de commencer la série de mesures afin de tenir compte des effets de cache et de JIT.

Pour chaque tri, on mesure l'heure avant l'appel de méthode et l'heure après, puis on fait la différence. Il faut faire attention à ne pas mesurer les temps d'affichage ou de génération des tableaux.

Pour être plus précis, il aurait fallu effectuer chaque expérimentation plusieurs fois et faire des moyennes pour limiter les facteurs extérieurs.

Résultats

Les résultats suivants ont été effectué sur des tableaux de taille comprise entre 5000 et 50 000 éléments (int) sur une machine de bureau (Xeon E5520) avec Java 1.7.0_10. Les courbes ont été dessinées avec Gnuplot.

Sur la première figure, on voit que le tri à bulle est de loin le plus lent de tous. Sélection et Insertion ont de bien meilleures performances que le tri à bulle, ce qui est plus surprenant.

Comme attendu, les tris récursifs sont beaucoup plus rapides. Un zoom permet de vérifier le comportement du tri rapide et du tri fusion. On remarque un léger avantage pour le tri rapide, probablement du au fait qu'il n'utilise pas de tableau intermédiaire, contrairement au tri fusion.

Le cas du tri à bulle est intéressant. Pour rappel, la complexité algorithmique de ce tri est la même que pour Insertion ou Sélection, c'est à dire O(N²). Même si la notation grand-O masque les facteurs constants, la différence parait énorme. Il faut chercher la cause du coté d'un autre phénomène. Pour cela, nous utilisons l'outil perf qui permet sous Linux d'accéder aux compteurs du processeur pour mesurer très précisément le comportement d'un programme. On remarque la chose suivante, pour des tableaux de taille 1000 à 10 000.

Selection : 3,212,059 branch-misses (0.59% of all branches)

Bulle : 278,812,960 branch-misses (8.11% of all branches)

La prédiction de branchement est un mécanisme qui permet au processeur de deviner quelles seront les prochaines instructions à exécuter quand il rencontre un branchement. Ça lui permet de les chercher en mémoire alors même qu'il n'a pas fini d'exécuter les instructions en cours. C'est une sorte de pari et si le processeur se trompe, alors il doit annuler ce qu'il a fait, ce qui coûte chère. Les branches apparaissent partout dans le code où il y a des instructions de flot comme while, for, if ... Visiblement ici, le processeur a beaucoup de mal à prévoir ce qu'il faut faire quand il rencontre une branche dans le tri à Bulle. C'est un problème bien connu du tri à Bulle et qui a été analysé par exemple ici.

Conclusion

Implémenter les algorithmes classiques de tri en Java est relativement simple, une fois qu'on a l'habitude de manipuler les tableaux. Ça permet de vérifier expérimentalement l'impact de la complexité sur les performances. Mais plus amusant, les expériences montrent que la complexité théorique n'est pas forcément suffisante pour prédire les performances d'un algorithme. Sa mise en pratique peut faire intervenir des mécanismes qui augmenteront ou au contraire diminueront drastiquement ses performances.