Skip navigation
We just discovered faster sorting algorithms!
0:00 / 1:32

We just discovered faster sorting algorithms!

Santiago

@svpino456K followers

Visit on X
1,330 likesDownloadOriginal post

407,826 views

We just discovered faster sorting algorithms! Here is a 60-second explanation of what happened: DeepMind turned the sorting problem into a puzzle, where the goal of an agent is to organize a list of instructions to find a correct and efficient algorithm. Think Tetris, but using lines of code. They used Deep Reinforcement Learning to train the agent who only wins the game if it finds an efficient algorithm. They called it "AlphaDev," and it didn't disappoint: AlphaDev found shorter and faster solutions for several sorting variants that we use trillions of times daily! This is a big deal. Conceptually, sorting is still an O(N log N) problem; Deepmind didn't change that. But practically speaking, and thanks to AlphaDev, we have code that runs faster. You should read their paper. They compared the current version of these algorithms and the new version they discovered. In some cases, they made significant improvements. Some people aren't happy with the way DeepMind is promoting this work. They argue the results aren't as breathtaking as the headlines claim. We can discuss their marketing, but this is undoubtedly a significant step with a real impact and the potential to generalize to more areas. The new algorithms that AlphaDev found seem trivial, yet no human found them before. That's the true power of Artificial Intelligence.

8 Comments

Comments from the original post on X (Twitter)

  • Santiago's profile picture

    @svpino

    Here is a link to DeepMind's paper:

    93 likes

  • Santiago's profile picture

    @svpino

    Isn't this a new algorithm?

    5 likes

  • Santiago's profile picture

    @svpino

    Thanks for the link! I forgot to include it.

    3 likes

  • RedEyed's profile picture

    @red__eyed

    It should be noted that it's 70% faster on sequences of length less than 5 elements, and 1.7% speedup on sequences more than 250k elements

    31 likes

  • Santiago's profile picture

    @svpino

    Correct.

    3 likes

  • Santiago's profile picture

    @svpino

    Yup, I read that post. I don't feel comfortable mixing their marketing with their technical accomplishments. I understand those who argue they leaned too much into hype. I do not understand those minimizing the importance of what they did.

    2 likes

  • 𝗝 𝟯 𝟯 𝗣 𝟰 | 𝗷𝟯𝟯𝗽𝟰.𝗲𝘁𝗵's profile picture

    @J33P4

    This is important in terms of what could be achieved in other problems, but this is definitely overhyped by Deepmind. Nvidia is doing stuff like this with hardware optimisation and they don’t try to publish it in Nature. They just do it and make faster chips faster.

    16 likes

  • Santiago's profile picture

    @svpino

    I think we can argue about their marketing, but it's not fair to subtract importance from their work.

    5 likes