AlphaDev 发现新的排序算法，直接突破人类极限

This topic created in 1086 days ago, the information mentioned may be changed or developed.

https://mp.weixin.qq.com/s/kHahnmVZP3qD_TGKrlXQ5Q

...
在一项新发表于《自然》杂志的研究中，DeepMind 团队介绍了一种新的人工智能（ AI ）系统AlphaDev ，它通过使用深度强化学习，发现了更快的排序算法。这些全新的算法超越了现有的、最优的、由人类科学家在数十年时间里磨炼出的算法。
...
最终，AlphaDev 发现了新的、更快的排序算法。对于较短的序列，AlphaDev 的算法可以将速度提高 70%。但对于超过 25 万个项的序列，累积节省的时间只能提高 1.7%。
...

元芳，你怎么看？

alphadev

算法

排序

序列

14 replies 2023-06-09 13:37:44 +08:00

Wenbobobo

Jun 9, 2023 via Android

https://www.zhihu.com/answer/3064456593
“ 这个 99% 没用, 即便是分治类型的排序算法, 这也不在分解的关键路径上.派发开销能不能赚回来都不知道, 反正他们给 LLVM 提的 pr 还搁置着, 效果存疑. ”

GPLer

Jun 9, 2023

这个好像只是优化汇编，并没有发明新的排序算法。。。

iamqk

Jun 9, 2023

@Wenbobobo 没看那个回复的评论？

iamqk

Jun 9, 2023

shyrock

Jun 9, 2023

知乎的回答说到了点上。
这不是有没有新算法的问题，而是能否颠覆信息论的问题。

在信息论的框架下，各种排序算法都有其适用的场景（有不同的最坏情况），并且在效率上都有一个共同的上限。
这种公众号文章，要么是揣着明白装糊涂骗流量，要么就是计算机民科。

Chinsung

Jun 9, 2023

现有的排序算法都是基于数据证明的，AI 除非发现新的数学，不然在时间复杂度上我个人觉得不会有什么太离谱的跨越

Chinsung

Jun 9, 2023

@Chinsung 数学证明

lusi1990

Jun 9, 2023

一眼假，现在计算机的排序早就比人类快了

leimao

Jun 9, 2023

他这个优化的是排序算法 Master Theorem 递归公式里的常数项，也就是 sort_2, sort_3, sort_4 ，这种的，不影响长序列的 asymptotic complexity 。理论意义不如他们去年发现的 Matrix Multiplication 的有着更好 asymptotic complexity 的算法。

leimao

Jun 9, 2023

另外，我看网上有人直接问 ChatGPT 让它做同样的优化，ChatGPT 也能得到同样的优化方法。（不过不晓得他们玩的那个版本的 ChatGPT 有没有看过这个文献）

leimao

Jun 9, 2023

[Strassen Algorithm]( https://leimao.github.io/blog/Strassen-Algorithm/)曾被认为是 Matrix Multiplication 在 asymptotic complexity 理论上最优的算法，但是去年 DeepMind 的 RL 搜索出了一个更好的，那个其实更有意思。

leimao

Jun 9, 2023

https://leimao.github.io/blog/Strassen-Algorithm/

leimao

Jun 9, 2023

另外，**基于比较**的排序算法 asymptotic complexity 理论最优就是 O(NlogN)，这个是不可能被打破的。

idealhs

Jun 9, 2023

你那边的楞类鸡腺是不是有点低