DeepMind推驚世排序演算法，C++函式庫忙更新！

點擊參加51CTO網站內容問卷

編譯| 王瑞平、言徵

AlphaGo又有「小弟」加入了!

#Google DeepMind把Alpha系列「卷」到了排序演算法上，重磅推出AlphaDev。

它好比一種“開發秘法”，透過使用強化學習AI發現排序演算法和雜湊演算法，強行把人類程式設計師設計的演算法分別提速約70%和30%。

研究成果一推出，瞬間點燃軟體圈！一下子，全球數以百萬計的軟體運行速度飆升，直接超越了科學家和工程師幾十年來的成果，十年未更新的LLVM標準C 庫都更新了。

（來源：Nature）

這也是繼Google兩AI部門合體後推出的顛覆性技術。論文以《使用深度強化學習模型發現更快排序演算法》（Faster sorting algorithms discovered using deep reinforcement learning）為題發表於Nature。論文的第一作者是DeepMind的電腦科學家Daniel Mankowitz。

1、演進：排序演算法的由來

排序是一種將許多項目按特定順序組織起來的方法，例如，按照字母順序排列三個字母，從最大到最小的順序排列五個數字或對包含數百萬筆記錄的資料庫進行排序。

排序法最早可追溯至二到三世紀，仍在不斷演進。最初，學者們手工將亞歷山大圖書館書架上數千本書按照字母序進行歸納。

工業革命之後，人們發明了可自行分類的機器，即，將資訊儲存在穿孔卡上的製表機器中，用於收集1890年美國人口普查的結果。

20世紀50年代，商用電腦開始興起，也隨即產生了排序演算法。輸入一些未排序的數字到排序演算法中，它會產生一個已排序的數字序列。

目前，各個地方的程式碼庫中仍在使用許多不同的排序技術和演算法來處理大量資料。      

經過數十年的研究和開發，這些排序演算法的效率不斷提高，得到電腦科學家和程式設計師的認可。但是，對其進一步改進仍具有重大挑戰。

2、重頭戲：如何用AlphaDev產生新排序演算法？

研究人員最初用AlphaDev產生新演算法的目的是高效率完成給定任務。

AlphaDev建構了全新的演算法，不是基於先前的演算法進行開發，因此可以視為原創。在此過程中，它應用了彙編程式碼的中間語言。 AlphaDev可以更容易創造高效演算法，因為該語言更接近電腦二進位指令。

具體來講，AlphaDev每次產生一個指令，然後測試其輸出正確與否，同時還在模型中設定要求產生最短演算法。

當被要求重新設計排序演算法時，AlphaDev隨機產生比現有演算法快70%的新排序演算法，可同時將五個資料排序。在對25萬個資料進行排序時，它也比最好的演算法快1.7%。

這項創新會對全球演算法產生巨大影響，因為各種常見軟體都廣泛使用排序演算法。 DeepMind has open-sourced them and integrated them into the Libc standard library.。

根據DeepMind的研究者描述：「由於指令組合數量龐大，看似簡單的研究過程難度極大。」

3、緣起：在玩遊戲中找到最佳演算法 

更進一步地說，AlphaDev是一種更先進的模型，它是基於AlphaZero的結構而設計。而AlphaZero先前是DeepMind的強化學習模型，曾在圍棋、西洋棋和其它棋類遊戲中擊敗了世界冠軍。

透過此實驗，新模型AlphaDev發揮出從玩遊戲轉移到解決科學問題以及從實驗模擬轉移到現實世界應用的獨特優勢。

研究者將排序模擬為單人“組裝遊戲”，以訓練AlphaDev發現新演算法。在每個遊戲回合中，AlphaDev都能觀察到產生的演算法和包含在CPU中的信息，然後選擇一條指令加入演算法中走出每一步棋。

論文中提到，彙編遊戲非常困難，因為AlphaDev必須能夠有效地搜尋到大量可能的指令組合以獲取可以排序的演算法。

指令組合數量類似於宇宙中粒子數量或國際象棋(10120局)和圍棋(10700局)中可能走法的組合數量，每個錯誤的舉動將會使整個演算法失效。

然後，該模型輸出演算法並將其與預期輸出進行比較，根據演算法的正確性和延遲時間獎勵代理。

在建立演算法時，每次輸入一個指令，AlphaDev透過比較輸出演算法與預期結果檢查正確性（對於排序演算法，這意味著輸入無序的數字後能夠輸出正確排序的數字）。

模型會獎勵AlphaDev對數字的正確排序以及它的高效率。最終AlphaDev通過發現更準確的、更快的程序贏得了比賽。

4、演算法創新：交換移動和複製移動指令序列

AlphaDev不僅產生了更快演算法，還創新出兩種指令序列。

具體來講，它產生的排序演算法包括交換移動和複製移動兩個新的指令序列，每次使用時都會保存一條指令。研究者稱之為「AlphaDev的交換移動和複製移動」。

這種新穎的方法讓人想起AlphaGo的「第37步」—「反直覺」下棋法，震驚了旁觀者並造成一位傳奇棋手的失敗。

透過交換移動和複製移動指令序列，AlphaDev跳過了一個步驟，以一種看起來像錯誤但實際上是捷徑的方式完成目標。這意味著AlphaDev具備發現初始解決方案並嘗試改進電腦科學演算法的能力。

5、測試：推​​廣和改進雜湊演算法

研究人員在發現更快的排序演算法後，試圖將其應用到另一種電腦科學演算法——散列演算法的推廣和改進上。

雜湊演算法是計算中的一種基本演算法，用於檢索、儲存和壓縮資料。就像圖書館員使用分類系統定位某本書一樣，雜湊演算法幫助使用者知道他們要找的是什麼以及在哪裡可以找到它。

這些演算法能夠取得特定金鑰(例如，使用者名稱「Jane Doe」)的資料並對其進行雜湊排序－將原始資料轉換為唯一字串(例如，1234ghty)。

電腦使用該雜湊快速檢索與金鑰相關的數據，而不是搜尋所有數據。

研究人員將AlphaDev應用於資料結構中最常用的雜湊演算法之一以嘗試發現更快的演算法。當將其應用於散列函數的9-16位元組範圍時，AlphaDev產生的演算法速度快了30%。

今年早些時候，AlphaDev生成的新雜湊演算法曾被發佈到開源的Abseil庫中，全世界數以百萬計的開發人員都可以使用，估計它現在每天被使用數萬億次。

6、蓄勢：邁出開發AGI的第一步  

透過優化“排序和雜湊演算法”，AlphaDev展示出生成不同實用新演算法的能力。

這也是AlphaDev朝著開發通用人工智慧（AGI）工具邁出的第一步，透過類似的AI工具還可以幫助優化整個運算生態系統並解決其它有益於社會的問題。

雖然在低階彙編指令空間中最佳化演算法的功能非常強大，但它也有其限制。目前，團隊正在研究AlphaDev在高階語言（如C ）中優化演算法的能力，這將對開發人員更有益。

總之，希望這些新發現能激勵開發人員創造新技術和方法、進一步優化基本演算法，創造更強大、更永續的運算生態系統。

7、開源：AI優化程式碼的里程碑突破

之前，排序演算法每天都會被使用數萬億次。隨著計算需求的增長，人們對演算法的效能要求越來越高。雖然人類工程師發現不同的排序演算法，但經過數十年的最佳化，很難再有突破，也滿足不了日益增長的需求。

如今，AlphaDev發現了一種更快的排序演算法，可對資料進行排序。

新排序演算法無所不能，既可應用於線上搜尋結果和社交貼文進行排名，也可在電腦和手機上處理資料。

值得慶賀的是，新排序演算法已在主C 庫中開源。世界各地數以百萬的開發人員和公司目前可將其用於雲端運算、線上購物、供應鏈管理等。

總之，使用人工智慧工具優化演算法將徹底改變傳統程式設計方式。這是十多年來第一次對排序庫進行更改，第一次將強化學習模型設計的演算法添加到排序庫中，因此成為了使用人工智慧優化程式碼的里程碑式突破。

8、用戶：可能只是噱頭 

對於該研究成果用戶褒貶不一，Twitter上讚美的聲音居多：

##學習基本排序任務是程式設計師早期就掌握的技能之一，這項技能提高了70%的速度。看到利用AI在我們都依賴的演算法和函式庫中進行重大加速，真是令人興奮」。

「很快，普通人就可以成為高級程式設計師」。

「有趣的方法，從組裝等級開始優化」！

但是，也有的程式設計師認為這只是個噱頭，DeepMind誇大了該演算法的功能。

首先就是從效率的角度，它只統計了演算法的延遲，而非真正改變了時間複雜度。

而且，它並沒有真正改變排序，這種操作常見於各種其它程式碼庫。

參考資料：

1.https://www.nature.com/articles/s41586-023-06004-9

2.https://www.deepmind.com/blog/alphadev -discovers-faster-sorting-algorithms

3.https://www.deepmind.com/blog/optimising-computer-systems-with-more-generalised-ai-tools

4 .https://twitter.com/demishassabis

#######

以上是DeepMind推驚世排序演算法，C++函式庫忙更新！的詳細內容。更多資訊請關注PHP中文網其他相關文章！