Deepmind Alphadev: Faster sorting algorithms discovered using deep RL (nature.com)

Article summary

Researchers at Deepmind used deep reinforcement learning to discover new sorting algorithms that outperform existing human-designed algorithms. The new algorithms were discovered by formulating the task of finding a better sorting routine as a single-player game, which was then played by a learning agent called AlphaDev. The discovered algorithms have been integrated into the LLVM standard C++ library. The approach has the potential to be applied to other domains, showcasing its generality.

Main themes

• sorting algorithms
• deep reinforcement learning
• algorithmic complexity
• practical performance
• cache locality
• big-O notation

What commenters say

• Some commenters argue that the improvement in sorting algorithms is not significant because it does not change the overall time complexity of the algorithm.
• Others counter that in practice, the actual running time of an algorithm is more important than its theoretical time complexity.
• There is disagreement about whether heap sort is the fastest sorting algorithm, with some arguing that it is not necessarily the case.
• Some commenters point out that radix sort can be faster than comparison-based sorting algorithms for certain types of data.
• The importance of considering factors such as cache locality and memory access patterns when evaluating the performance of algorithms is highlighted.
• Some argue that the big-O notation is not the only measure of an algorithm's speed, and that actual running time is a more relevant metric.
• Others emphasize that the big-O notation is a fundamental concept in computer science that provides a way to compare the scalability of different algorithms.