Des informaticiens améliorent la fonction de tri de Python

arXiv (2022). DOI : 10.48550/arxiv.2209.06909″ width=”800″ height=”349″/>

Des informaticiens de l’Université de Liverpool ont résolu un casse-tête algorithmique de longue date pour accélérer un élément de base de Python, le langage de programmation le plus populaire et la base des systèmes d’intelligence artificielle modernes.

La découverte a abouti à une meilleure solution pour trier les listes en Python, appelée Powersort, qui a été implémentée dans Python 3.11, la dernière version publiée en octobre.

Powersort organise les listes d’objets dans l’ordre croissant par les fonctions “list.sort” et “sorted” et le Dr Sebastian Wild, maître de conférences au département d’informatique de l’Université de Liverpool, est responsable de son invention.

Le Dr Wild avait étudié TimSort, un algorithme de tri personnalisé inventé par Tim Peters, un développeur Python influent, et plus particulièrement sa politique de fusion, qui détermine l’ordre dans lequel les exécutions détectées sont successivement “fusionnées” pour former des exécutions plus longues, jusqu’à ce que finalement la liste est entièrement trié.

Le Dr Wild a été surpris de voir à quel point sa politique de fusion était mal comprise, car il y avait même eu un bogue algorithmique et un problème de sécurité potentiel qui y était associé. Il s’est avéré que ce composant clé s’est avéré par la suite défectueux.

Une discussion entre le Dr Wild et son superviseur postdoctoral de l’époque, le professeur Ian Munro de l’Université de Waterloo, au Canada, a révélé qu’un algorithme théorique des années 1970 fournissait la solution optimale au problème de la recherche de bons ordres de fusion.

Cette découverte a conduit à la naissance de “Powersort”, qui a été initialement publié lors du Symposium européen sur les algorithmes 2018 et a été examiné plus en détail par la communauté Python avant d’atteindre l’implémentation de référence Python.

Le Dr Wild a déclaré : “Je suis ravi que mes recherches aient été mises en pratique et implémentées dans Python 3.11. Je suis tombé sur la solution pour trouver de bonnes commandes de fusion grâce à mon travail d’enquête sur Timsort. Une semaine après avoir trouvé l’homme de 50 ans algorithme, ‘Powersort’ est né.”

“Je suis très heureux que Tim Peters lui-même ait intégré notre idée dans l’implémentation de référence CPython. Son implémentation Timsort est un chef-d’œuvre d’ingénierie algorithmique, et personne ne connaît ce code comme lui.”

Carl Friedrich Bolz-Tereick, membre de la Python Software Foundation et développeur principal de PyPy, une implémentation alternative de Python, a ajouté : « Powersort est un excellent exemple de la façon dont la nature open source de Python nous permet d’apporter très rapidement des recherches de pointe résultats dans une utilisation en production pour tout le monde. Lorsque j’ai entendu parler de Powersort, j’ai pu l’inclure dans PyPy en quelques jours.

“Avec la sortie officielle de Python 3.11 en octobre, des centaines de millions d’utilisateurs apprécieront désormais le tri de plus en plus rapide. Même si l’amélioration pour de nombreuses entrées est minime, le nombre d’installations Python peut entraîner des économies d’énergie significatives sur un échelle globale.”

Timsort est également utilisé dans d’autres plates-formes logicielles importantes, notamment les bibliothèques d’exécution Java et Android, utilisées dans la plupart des smartphones, et le moteur JavaScript V8 utilisé dans Google Chrome et node.js, pilotant une grande partie des applications Web modernes qui peuvent toutes potentiellement bénéficier de Powersort. .

Le Dr Wild continue de mener des recherches sur le tri et il vient de terminer de travailler sur une amélioration de Powersort, fusionnant désormais quatre passages simultanément à chaque étape.

L’étude est publiée sur le arXiv serveur de préimpression.