AlphaDev de DeepMind découvre un algorithme de tri plus rapide

• Considérant qu’il était difficile d’obtenir des améliorations au niveau des langages C/C++, l’équipe a tenté d’optimiser au niveau assembleur
• Comme dans un jeu, l’algorithme explore sans cesse des solutions pour produire le résultat attendu
• Par rapport à la bibliothèque de tri de LLVM libc++, il affiche des performances 70 % plus rapides sur de petites tailles, et 1,7 % plus rapides sur des séquences de plus de 250 000 éléments
• Comme la plupart des opérations de tri portent sur de courtes séquences, l’accent a été mis sur ce point
• Il ne s’agit pas seulement d’être plus rapide : l’approche montre une ingéniosité comparable au 37e coup d’AlphaGo
• Des améliorations sont également en cours sur les algorithmes de hachage

[kuroneko]

C’est vraiment fascinant de voir que l’IA peut aussi découvrir de meilleurs algorithmes.

[dbs0829]

Il semble qu’il y ait récemment pas mal de tentatives pour trouver aussi les optimiseurs utilisés en deep learning de cette manière. Et les performances sont bonnes, en plus.

[spark]

Au lieu de dire que « la plupart des tris se produisent sur de courtes séquences, donc ils se sont davantage concentrés là-dessus », ils ont simplement entraîné le système à découvrir des algorithmes en assembleur pour trier un nombre fixe de valeurs — 3, 4, ... jusqu’à 8.

[disjukr]

À voir l’article original, on dirait bien que les chercheurs qui ont créé AlphaDev l’ont entraîné avec cette intention.

Nous nous sommes concentrés sur l’amélioration des algorithmes de tri pour des séquences plus courtes de trois à cinq éléments. Ces algorithmes font partie des plus largement utilisés, car ils sont souvent appelés de nombreuses fois dans le cadre de fonctions de tri plus vastes. Les améliorer peut conduire à une accélération globale du tri, quel que soit le nombre d’éléments.