这是一个创建于 538 天前的主题，其中的信息可能已经有所发展或是发生改变。
https://mp.weixin.qq.com/s/kHahnmVZP3qD_TGKrlXQ5Q
...
在一项新发表于《自然》杂志的研究中，DeepMind 团队介绍了一种新的人工智能（ AI ）系统——AlphaDev ，它通过使用深度强化学习，发现了更快的排序算法。这些全新的算法超越了现有的、最优的、由人类科学家在数十年时间里磨炼出的算法。
...
最终，AlphaDev 发现了新的、更快的排序算法。对于较短的序列，AlphaDev 的算法可以将速度提高 70%。但对于超过 25 万个项的序列，累积节省的时间只能提高 1.7%。
...
元芳，你怎么看？
...
在一项新发表于《自然》杂志的研究中，DeepMind 团队介绍了一种新的人工智能（ AI ）系统——AlphaDev ，它通过使用深度强化学习，发现了更快的排序算法。这些全新的算法超越了现有的、最优的、由人类科学家在数十年时间里磨炼出的算法。
...
最终，AlphaDev 发现了新的、更快的排序算法。对于较短的序列，AlphaDev 的算法可以将速度提高 70%。但对于超过 25 万个项的序列，累积节省的时间只能提高 1.7%。
...
元芳，你怎么看？
 |
1
Wenbobobo 2023-06-09 08:32:00 +08:00 via Android
https://www.zhihu.com/answer/3064456593
“ 这个 99% 没用, 即便是分治类型的排序算法, 这也不在分解的关键路径上.派发开销能不能赚回来都不知道, 反正他们给 LLVM 提的 pr 还搁置着, 效果存疑. ” 👀 |
 |
2
GPLer 2023-06-09 08:57:45 +08:00
这个好像只是优化汇编，并没有发明新的排序算法。。。
|
 |
4
iamqk OP <img alt="搞笑回复" src="http://picx.zhimg.com/80/v2-9ba345c1a7d0e811510083e92d28153c_1440w.webp?source=1940ef5c">
|
 |
5
shyrock 2023-06-09 09:26:26 +08:00  1
知乎的回答说到了点上。
这不是有没有新算法的问题，而是能否颠覆信息论的问题。 在信息论的框架下，各种排序算法都有其适用的场景（有不同的最坏情况），并且在效率上都有一个共同的上限。 这种公众号文章，要么是揣着明白装糊涂骗流量，要么就是计算机民科。 |
 |
6
Chinsung 2023-06-09 11:55:28 +08:00
现有的排序算法都是基于数据证明的，AI 除非发现新的数学，不然在时间复杂度上我个人觉得不会有什么太离谱的跨越
|
 |
8
lusi1990 2023-06-09 13:10:17 +08:00
一眼假， 现在计算机的排序早就比人类快了
|
 |
9
leimao 2023-06-09 13:27:24 +08:00
他这个优化的是排序算法 Master Theorem 递归公式里的常数项，也就是 sort_2, sort_3, sort_4 ，这种的，不影响长序列的 asymptotic complexity 。理论意义不如他们去年发现的 Matrix Multiplication 的有着更好 asymptotic complexity 的算法。
|
|
10
leimao 2023-06-09 13:28:54 +08:00
另外，我看网上有人直接问 ChatGPT 让它做同样的优化，ChatGPT 也能得到同样的优化方法。（不过不晓得他们玩的那个版本的 ChatGPT 有没有看过这个文献）
|
|
11
leimao 2023-06-09 13:31:21 +08:00
[Strassen Algorithm]( https://leimao.github.io/blog/Strassen-Algorithm/)曾被认为是 Matrix Multiplication 在 asymptotic complexity 理论上最优的算法，但是去年 DeepMind 的 RL 搜索出了一个更好的，那个其实更有意思。
|
|
12
leimao 2023-06-09 13:31:40 +08:00
|
|
13
leimao 2023-06-09 13:33:56 +08:00
另外，**基于比较**的排序算法 asymptotic complexity 理论最优就是 O(NlogN)，这个是不可能被打破的。
|
 |
14
idealhs 2023-06-09 13:37:44 +08:00
你那边的楞类鸡腺是不是有点低
|
Select Language