AlphaDev, da DeepMind, descobre algoritmos de ordenação mais rápidos

• Considerando que seria difícil obter melhorias em linguagens no nível de C/C++, tentaram otimizar no nível de assembly
• Como em um jogo, o algoritmo explora continuamente respostas que correspondam à solução esperada
• Em comparação com a biblioteca de ordenação do LLVM libc++, apresentou desempenho 70% mais rápido em conjuntos menores e 1,7% mais rápido em sequências com mais de 250 mil itens
• Como a maior parte das ordenações ocorre em sequências curtas, o foco foi maior nesse ponto
• Não é apenas mais rápido: também mostra uma abordagem engenhosa comparável ao lance 37 do AlphaGo
• Também está melhorando algoritmos de hashing

[kuroneko]

É realmente impressionante que a IA também consiga encontrar algoritmos de ordenação melhores.

[dbs0829]

Pelo que vi, recentemente também têm sido feitas várias tentativas de encontrar optimizers usados em deep learning desse jeito. E o desempenho também é bom.

[spark]

"Em vez de algo como 'como a maioria das ordenações acontece em sequências curtas, vamos focar mais nisso', eles simplesmente o treinaram para descobrir algoritmos em assembly que ordenassem uma quantidade fixa de números — 3, 4, ... até 8."

[disjukr]

Olhando o texto original, parece que os pesquisadores que criaram o AlphaDev o treinaram com essa intenção em mente.

Nós nos concentramos em melhorar algoritmos de ordenação para sequências mais curtas de três a cinco elementos. Esses algoritmos estão entre os mais usados, porque muitas vezes são chamados repetidamente como parte de funções de ordenação maiores. Melhorá-los pode levar a um ganho geral de velocidade na ordenação de qualquer quantidade de itens.