今天小編分享的科學經驗：重現當年AlphaGo神來之筆！DeepMind新AI發現提速70%排序算法，十年都沒更的C++庫更新了，歡迎閲讀。
DeepMind 又雙叒叕帶着重磅成果登 Nature 了！
這一次，他們又一強化學習 AI，在計算機領網域最最最基礎的兩個算法上做了新突破：
一個是排序算法，發現了速度最高可提升 70%的新實現；
另一個是哈希算法，也找到了速度提高 30%的新方法。
不僅如此，該 AI 所用方法被稱為 " 重現當年 AlphaGo 的神來之筆 "，也就是看似違法直覺，實則一舉擊敗人類高手李世石的那次。
消息一出，立刻引爆學術圈，有網友就直呼：
沒想到這麼古老又基礎的算法還能被進一步改進。
而正是因為這一最新成果，十年都沒有更新的 LLVM 标準 C++ 庫都更新了，并且數十億人将會受益。
因為，無論是排序還是哈希，它們的應用場景從在線購物、雲計算到供應鏈管理等各個場景都能用到，每天會被調用上億次！
不過，如 DeepMind 所説：
大家千萬不要太興奮了，AI 的力量用于代碼效率提升才剛剛開始。
Alpha 家族 " 新貴 " 發現更快排序算法
這個 AI 名叫AlphaDev，屬于 Alpha 家族 " 新貴 "，并且基于 AlphaZero 打造（就是 2017 年擊敗世界冠軍的那個棋類 AI）。
它的發現并非基于現有算法，而是從最底層的匯編指令開始摸索的。
DeepMind 的研究員給它設計了一種單人 " 組裝 " 遊戲：
只要能夠搜索并選擇出合适的指令（下圖 A 流程），正确且快速地排好數據（下圖 B 流程），就能獲得獎勵。
但這個遊戲的挑戰不僅在于搜索空間的大小（可組合指令數相當于宇宙中的粒子數），也在于獎勵函數的性質，因為一條錯誤指令就可能會使整個算法失效。
AlphaDev 擁有兩個核心組件：學習算法和表示函數。
其中，學習算法主要是在強大的 AlphaZero 上擴展的，它可以結合 DRL 和随機搜索優化算法來進行巨量的指令搜索；主要的表示函數則基于 Transformer，它能夠抓住匯編程式的底層結構，并表示成特殊的序列。
随着 AlphaDev 不斷地打怪更新，研究員還會限制它能執行的步數，以及待排序列的長度。
最終，AlphaDev 發現了一種全新排序算法：
如果序列較短，相比人類基準排序算法，它能将速度提高 70%；如果序列長度超過 25000 個元素，則提高 1.7%。
（3-5 個元素的短序列排序其實使用非常廣泛，因為它能夠作為較大排序函數的一部分被多次調用。因此，只要改進了短序列，任意數量序列的整體排序速度都能得到提高。）
具體而言，該算法的創新主要在于兩種指令序列：
（1）AlphaDev Swap Move（交換移動）
（2）AlphaDev Copy Move（復制移動）
如下圖所示，左邊是利用了 min ( A,B,C ) 的原始 sort3 實現，右邊是通過 "AlphaDev Swap Move"，只需要 min ( A,B ) 的實現。能夠發現可以省掉一步指令，還只需要算出 A 和 B 的最小值即可。
作者表示，這種新穎的方法讓人想起當年AlphaGo 的 " 第 37 步 "——一種違反直覺的下法卻直接擊敗傳奇圍棋選手李世石，讓觀眾全都震驚不已。
同樣，AlphaDev 則是通過交換和復制移動，跳過了一個步驟，以一種看似錯誤但實際上是捷徑的方式達成目标。
如下圖所示，在對 8 個元素進行排序的算法中，AlphaDev 也同樣利用 "AlphaDev Copy Move"，用 max ( B, min ( A, C ) ) 替換了原始實現中更為復雜的 max ( B, min ( A, C, D ) ) 指令，并且使整個算法的指令總數也減少了一步。
而在發現更快的排序算法後，作者也用 AlphaDev 試了試哈希算法，以此證明其通用性。
結果也沒有讓人失望，AlphaDev 在 9-16 字節的長度範圍内也實現了 30% 的速度提升。
和排序算法一樣，他們已将新方法集成到了 Abseil 庫中，全球數百萬開發人員現在都可以使用。
最後，作者表示，兩種新算法的實現顯示 AlphaDev 具有強大的發現原始解決方案的能力，并且将使我們進一步思考計算機領網域基礎算法的改進方式。
不過，由于本次研究中使用的匯編語言具有局限性，他們接下來還是打算嘗試 AlphaDev 在高級語言（如 C++）中優化算法的能力。
網友：不算發現新的排序算法
對于這一成果，不少人表示非常興奮。
如這位網友所説：
AlphaGo 驚豔全世界後，強化學習還能做什麼？還能做任何有實際意義的事情嗎？這就是答案。
不過這次，有不少人指出，DeepMind 似乎有誇大标題的嫌疑。
它計算的是算法延遲，而非傳統意義上的時間復雜度。如果真算時間復雜度，數據可能不好看。
它改進的并不是排序本身，而是在現代 CPU 上做新的排序（特别是短序列）。這種操作其實不算罕見，比如 FFTW、ATLAS 這些庫就是這麼做的。
同意，他們只是為特定 CPU 找到了更快的機器優化，并不算發現新的排序算法，方法本身很酷，但還不算開創性研究。
大家怎麼看？
論文地址：
https://www.nature.com/articles/s41586-023-06004-9
官方博客：
https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms?utm_source=twitter&utm_medium=social&utm_campaign=OCS
參考鏈接：
[ 1 ] https://twitter.com/demishassabis/status/1666545516941803520
[ 2 ] https://news.ycombinator.com/item?id=36228125
[ 3 ] https://twitter.com/DeepMind/status/1666462540367372291
