Vincent Jugé améliore l’algorithme au cœur de Python, Java et Android
En modifiant seulement quatre lignes de code, Vincent Jugé du LIGM surpasse les performances de l’algorithme de tri de référence : Timsort. Il présente sa nouvelle version, Adaptative Shivers Sort, lors de la conférence SODA20 à Salt Lake City, dans l’espoir de remplacer le vénérable algorithme.
Les algorithmes ont aussi leurs propres légendes, mais résistent-elles à un examen scientifique ? Vincent Jugé, maître de conférences au Laboratoire d'Informatique Gaspard-Monge (LIGM - CNRS/Université Paris-Est Marne-la-Vallée/ESIEE Paris/École des Ponts ParisTech), étudie ainsi leurs fondements théoriques afin de les améliorer. Avec Adaptative Shivers Sort, il propose une version supérieure de Timsort1 , extrêmement prisé pour le tri de données. Le tri de données est une opération de base qui est utilisée dans la plupart des algorithmes qui manipulent les données (parce que la plupart des autres traitements comme la consultation ou l'analyse sont plus efficaces quand les données sont triées). Ses travaux sont présentés à la conférence ACM-SIAM SODA202 , qui se tient du 5 au 8 janvier à Salt Lake City.
Conçu en 2002 par l’ingénieur américain Tim Peters, Timsort s’est rapidement imposé comme une référence parmi les algorithmes de tri. Il est par exemple toujours au centre de langages de programmation tels que Python et Java, et donc de tout l’environnement Android. Timsort excelle lorsque les données sont déjà un peu triées, ce qui est en fait la situation dans la plupart des cas concrets.
Vincent Jugé prend pour exemple les finances de l’université. « Le comptable met quotidiennement ses fichiers à jour : il ajoute de nouvelles données dans un ensemble qui est déjà trié chronologiquement. » Timsort arrive alors mieux que n’importe quel algorithme à placer correctement ces entrées supplémentaires. Si jamais la base de données est complètement aléatoire, ce qui est pour lui le pire des cas, alors Timsort fait au moins aussi bien que ses concurrents.
Cette position de leader n’empêche pas les chercheurs de continuer à étudier cet algorithme. « Quand j’ai été recruté au LIGM, j’ai rejoint des collègues qui travaillaient déjà sur Timsort, explique Vincent Jugé. Comme il a été conçu par un ingénieur, il n’y avait pas beaucoup de théorie disponible à son sujet. » Ainsi, il a fallu attendre quinze ans après sa sortie pour que Vincent Jugé et ses confrères décrivent pourquoi Timsort est si efficace, ce qui n’était auparavant que constaté et accepté.
Les chercheurs du LIGM découvrent alors l’existence d’un bug de Java lié à Timsort, corrigé depuis, et que l’algorithme est jusqu’à 50 % moins efficace que l’optimal théorique qu’ils ont mesuré. Vincent Jugé se consacre donc à proposer une version supérieure : Adaptative Shivers Sort. En changeant seulement quatre lignes de code parmi un millier, cet algorithme frôle l’optimum et fait 33 % mieux que Timsort dans le pire des cas.
Cette amélioration des performances tient dans un tri préliminaire des nouvelles données. Une fois la première insérée de manière classique, les autres sont ajoutées par rapport à elle au lieu de l’être en reparcourant à chaque fois toute la base de données.
« Pour les opérations comptables à l’université, reprend comme exemple Vincent Jugé, on combine des listings chronologiques de salaires, d’immobilier ou de matériel pour obtenir une immense liste triée. » Timsort essaye d’identifier des plages pré-triées pour les fusionner, puis avance de proche en proche pour tout assembler. Il tente de trouver le meilleur ordre pour tout regrouper grâce à une approche heuristique, c’est-à-dire des approximations rapides, mais considérées comme suffisamment efficaces. Adaptative Shivers Sort puise ses performances dans l’amélioration de cette heuristique.
Vincent Jugé compte profiter de la conférence SODA20 pour faire connaître son algorithme, d’abord à un large panel de chercheurs, puis à des spécialistes du tri. En particulier, il espère toucher les développeurs de Python et de Java, pour savoir si Adaptative Shivers Sort pourrait officiellement remplacer Timsort. Cela dépendra des performances de l’algorithme sur leur banc d’essai, auquel les chercheurs n’ont pas accès, et de la faisabilité opérationnelle d’un tel changement.