Les algorithmes de tri et de hachage sont utilisés des milliards de fois chaque jour – et leur exigence d’efficacité croît avec l’augmentation de la demande computationnelle.
Dans un article publié dans Nature, les équipes de GoogleMind détaillent comment l’intelligence artificielle peut aider à transformer les pratiques. En substance, l’équipe a demandé à un modèle d’apprentissage profond par renforcement, AlphaDev, de trouver de meilleures routines algorithmiques de tri. Le modèle a été construit en s’inspirant d’AlphaZero et Alpha Go, deux IA spécialisées dans les jeux.
En travaillant sur les niveaux d’instructions de bas-niveau plutôt qu’à l’étape des langages de haut niveau (qu’est C++, comme Java ou Python), AlphaDev a produit un algorithme de tri plus efficace que ce qui avait jusque-là été humainement imaginé pour trier des séries de données, explique l’équipe de DeepMind dans un article de blog. L’algorithme en question s’est révélé 70 % plus rapide que le meilleur algorithme connu pour le tri d’une liste de cinq éléments. Un autre a fait 1,7 % plus rapide que l’existant pour trier une liste de 250 000 éléments. L’équipe a traduit les algorithmes en C++ et les a publiés en open source.
Commentaires (12)
#1
Vraiment impressionnant.
Il me semble hautement improbable qu’AlphaDev puisse trouver des complexités algorithmiques inférieures à ce qu’on a aujourd’hui, mais optimiser l’existant, c’est déjà un pas de géant. L’algo de tri est clairement le plus utilisé, ne serait-ce que dans le ranking des moteurs de recherche, des réseaux sociaux, des suggestions musicales sur Spotify et consorts…
J’avais vu un papier qui disait que les optimisations des algorithmes les plus utilisés pourraient permettre de pallier les limites de la loi de Moore en permettant tout de même d’avoir des temps de traitement grandement réduits pour une même puissance de calculs.
Impatient de lire les prochaines annonces de Google sur ce sujet.
#1.1
Ou tout simplement partout… Tri des articles de NextInpact par date ? Tri par prix, pertinence, quoi que ce soit d’autre sur un site de vente… tri tri tri. Y’en a partout, liste des employés par ordre alphabétique. C’est rare qu’on te donne une liste “aléatoire” ou “par ordre de création”.
Question que je me pose : impact sur la consommation énergétique à l’échelle mondiale ?
#2
C’est d’autant moins probable qu’on a les complexités optimales pour le tri (par comparaison).
Je suis d’ailleurs très surpris qu’on puisse faire mieux : l’optimal est en n.log(n) et on atteint cette borne (atteinte par le tri par tas et en moyenne par le tri rapide).
#3
Au contraire. Les résultats sont spectaculaires dans le cas anecdotique du tri de 5 entiers, mais l’amélioration obtenue devient négligeable asymptotiquement, là où c’est important.
Rien de nouveau : on sait déjà que pour de la micro-optimisation instruction par instruction, les méthodes automatiques le font très bien – c’est ce que fait la passe d’optimisation d’un compilateur, et c’est d’ailleurs pour ça que presque plus personne n’optimise de routine en assembleur –, mais pour la complexité asymptotique, c’est l’algorithme qui compte, et là, on n’est pas battus par la machine.
#4
Il faut aussi peut être tenir compte de la rapidité/consommation de mémoire pour l’ensemble des opérations et pas uniquement le nombres d’opération?
#5
“L’algorithme en question s’est révélé 70 % plus rapide que le meilleur algorithme connu pour le tri d’une liste de cinq éléments. Un autre a fait 1,7 % plus rapide que l’existant pour trier une liste de 250 000 éléments”
Il me semble avoir compris que c’est le meme algo qui donne ce résultat. Et c’est la manière dont fonctionne cet algo qui fait que ca marche pour 4 et + mais que ca marche bien surtout pour des petits ensembles. Vu que l’algo tri toujours les 3 premiers chiffres et change de manière de trier ensuite. Le 70% d’ailleurs ca doit être pour 4 et non 5.
#6
“If the length is three then it calls sort 3 to sort the first three numbers and returns. If, however, the length is greater than three, then it calls sort 3, followed by a simplified sort 4 routine that sorts the remaining unsorted number. It is this part of the routine that results in significant latency savings.”
#7
Comme le dit le billet de blog, DeepMind a trouvé une meilleure décomposition du code de haut-niveau en opérations élémentaires dans le cas très spécifique de cet algorithme de tri.
C’est davantage la création d’un “meilleur optimiseur LLVM dans le cas de cet algo de tri” qu’un meilleur algo de tri… tout court.
C’est d’ailleurs leur conclusion:
#8
La consommation mémoire des algos de tri ?!? Je ne sais pas à quel algo tu penses, mais pour les algos usuels, c’est négligeable.
#9
A l’échelle mondiale il y a beaucoup de données stockées dans des bases. Si le tri des données est une partie importante/couteuse du traitement, nulle doute qu’un admin a du créer un index qui permet de récupérer les données déjà triées.
exemple: Indexes and ORDER BY
#9.1
My bad. Effectivement normalement le tri n’est effectué qu’à l’insertion/mise à jour.
#10
Difficile à estimer. Mais d’après les auteurs, le code écrit par AlphaDev ayant été intégré dans LLVM est exécuté “des trillions de fois par jour” (cet à dire plus d’un milliard de milliards de fois par jour).
On parle souvent d’immense ensembles de données, mais dans la réalité ces APIs sont le plus souvent utilisés pour trier de petites listes (souvent moins de 16 éléments).
Les très gros ensembles de données n’utilisent pas
std::sort(), ils ont leurs propres outils spécialisés pour ça.Donc en pratique oui ça aura un impact (probablement insignifiant relativement à notre consommation totale, mais pas négligeable dans l’absolu).