Name: Old Progger Dude 2023-06-08 11:16
Google finds faster sorting algorithm using deep reinforcement learning
ggchappell 1404 points
The three new sorting algorithms are for sorting lists of size 3, 4, and 5, respectively. This is interesting, but if you're reading this thinking that AI techniques have found replacements for Merge Sort or Introsort or something like that, then you're going to be disappointed.
currentscurrents 946 points
Yes, but they are primitives used to implement those larger sort algorithms.
https://old.reddit.com/r/programming/comments/143gskm/google_finds_faster_sorting_algorithm_using_deep
Faster sorting algorithms discovered using deep reinforcement learning
Abstract
Fundamental algorithms such as sorting or hashing are used trillions of times on any given day. As demand for computation grows, it has become critical for these algorithms to be as performant as possible. Whereas remarkable progress has been achieved in the past, making further improvements on the efficiency of these routines has proved challenging for both human scientists and computational approaches. Here we show how artificial intelligence can go beyond the current state of the art by discovering hitherto unknown routines. To realize this, we formulated the task of finding a better sorting routine as a single-player game. We then trained a new deep reinforcement learning agent, AlphaDev, to play this game. AlphaDev discovered small sorting algorithms from scratch that outperformed previously known human benchmarks. These algorithms have been integrated into the LLVM standard C++ sort library. This change to this part of the sort library represents the replacement of a component with an algorithm that has been automatically discovered using reinforcement learning. We also present results in extra domains, showcasing the generality of the approach.
https://www.nature.com/articles/s41586-023-06004-9
ggchappell 1404 points
The three new sorting algorithms are for sorting lists of size 3, 4, and 5, respectively. This is interesting, but if you're reading this thinking that AI techniques have found replacements for Merge Sort or Introsort or something like that, then you're going to be disappointed.
currentscurrents 946 points
Yes, but they are primitives used to implement those larger sort algorithms.
https://old.reddit.com/r/programming/comments/143gskm/google_finds_faster_sorting_algorithm_using_deep
Faster sorting algorithms discovered using deep reinforcement learning
Abstract
Fundamental algorithms such as sorting or hashing are used trillions of times on any given day. As demand for computation grows, it has become critical for these algorithms to be as performant as possible. Whereas remarkable progress has been achieved in the past, making further improvements on the efficiency of these routines has proved challenging for both human scientists and computational approaches. Here we show how artificial intelligence can go beyond the current state of the art by discovering hitherto unknown routines. To realize this, we formulated the task of finding a better sorting routine as a single-player game. We then trained a new deep reinforcement learning agent, AlphaDev, to play this game. AlphaDev discovered small sorting algorithms from scratch that outperformed previously known human benchmarks. These algorithms have been integrated into the LLVM standard C++ sort library. This change to this part of the sort library represents the replacement of a component with an algorithm that has been automatically discovered using reinforcement learning. We also present results in extra domains, showcasing the generality of the approach.
https://www.nature.com/articles/s41586-023-06004-9