V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
iamqk
V2EX  ›  分享发现

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

  •  1
     
  •   iamqk · 294 天前 · 3195 次点击
    这是一个创建于 294 天前的主题,其中的信息可能已经有所发展或是发生改变。
    https://mp.weixin.qq.com/s/kHahnmVZP3qD_TGKrlXQ5Q

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

    元芳,你怎么看?
    14 条回复    2023-06-09 13:37:44 +08:00
    Wenbobobo
        1
    Wenbobobo  
       294 天前 via Android
    https://www.zhihu.com/answer/3064456593
    “ 这个 99% 没用, 即便是分治类型的排序算法, 这也不在分解的关键路径上.派发开销能不能赚回来都不知道, 反正他们给 LLVM 提的 pr 还搁置着, 效果存疑. ”
    👀
    GPLer
        2
    GPLer  
       294 天前
    这个好像只是优化汇编,并没有发明新的排序算法。。。
    iamqk
        3
    iamqk  
    OP
       294 天前
    @Wenbobobo 没看那个回复的评论?
    iamqk
        4
    iamqk  
    OP
       294 天前
    shyrock
        5
    shyrock  
       294 天前   ❤️ 1
    知乎的回答说到了点上。
    这不是有没有新算法的问题,而是能否颠覆信息论的问题。

    在信息论的框架下,各种排序算法都有其适用的场景(有不同的最坏情况),并且在效率上都有一个共同的上限。
    这种公众号文章,要么是揣着明白装糊涂骗流量,要么就是计算机民科。
    Chinsung
        6
    Chinsung  
       294 天前
    现有的排序算法都是基于数据证明的,AI 除非发现新的数学,不然在时间复杂度上我个人觉得不会有什么太离谱的跨越
    Chinsung
        7
    Chinsung  
       294 天前
    @Chinsung 数学证明
    lusi1990
        8
    lusi1990  
       294 天前
    一眼假, 现在计算机的排序早就比人类快了
    leimao
        9
    leimao  
       294 天前
    他这个优化的是排序算法 Master Theorem 递归公式里的常数项,也就是 sort_2, sort_3, sort_4 ,这种的,不影响长序列的 asymptotic complexity 。理论意义不如他们去年发现的 Matrix Multiplication 的有着更好 asymptotic complexity 的算法。
    leimao
        10
    leimao  
       294 天前
    另外,我看网上有人直接问 ChatGPT 让它做同样的优化,ChatGPT 也能得到同样的优化方法。(不过不晓得他们玩的那个版本的 ChatGPT 有没有看过这个文献)
    leimao
        11
    leimao  
       294 天前
    [Strassen Algorithm]( https://leimao.github.io/blog/Strassen-Algorithm/)曾被认为是 Matrix Multiplication 在 asymptotic complexity 理论上最优的算法,但是去年 DeepMind 的 RL 搜索出了一个更好的,那个其实更有意思。
    leimao
        13
    leimao  
       294 天前
    另外,**基于比较**的排序算法 asymptotic complexity 理论最优就是 O(NlogN),这个是不可能被打破的。
    idealhs
        14
    idealhs  
       294 天前
    你那边的楞类鸡腺是不是有点低
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2892 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 13:52 · PVG 21:52 · LAX 06:52 · JFK 09:52
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.