重現當年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%。

短序列排序在實際中被廣泛使用，尤其作為較大排序函數的一個重要組成部分，被多次調用。只要改進了短序列，所有數量序列的排序速度都能提升。 )

具體而言，此演算法的創新主要在於兩種指令序列：

（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.php.cn/link/a3fefe83288ecb0e40ebe40b2bde29fe
官方部落格：https://www.php.cn/link/f5b2faa928f940f3f09a014f4aa

參考連結：
[1]https://www.php.cn/link/5383c7318a3158b9bc261d0b6996f7c2
[2]https:// www.php.cn/link/ecf9902e0f61677c8de25ae60b654669
[3]https://www.php.cn/link/0383314bf626052313b8275638fc

########ccc

以上是重現當年AlphaGo神來之筆！ DeepMind新AI發現提速70%排序演算法，十年都沒更的C++函式庫更新了的詳細內容。更多資訊請關注PHP中文網其他相關文章！