AI重寫排序演算法，速度快70%：DeepMind AlphaDev革新運算基礎，每天呼叫萬億次的函式庫更新了

「透過交換和複製移動，AlphaDev 跳過了一個步驟，以一種看似錯誤，但實際上是捷徑的方式連接項目。」這種前所未見、違反直覺的思想不禁讓人回想起2016 年那個春天。

七年前，AlphaGo 在圍棋上擊敗人類世界冠軍，如今 AI 又在程式設計上給我們上了一課。

今天凌晨，Google DeepMind CEO 哈薩克的兩句話引爆了電腦領域：「AlphaDev 發現了一種全新且更快的排序演算法，我們已將其開源到主要C 庫中供開發人員使用。這只是AI 提升程式碼效率進步的開始。」

##這一次，Google DeepMind 的全新強化學習系統AlphaDev 發現了一種比以往更快的雜湊演算法，這是電腦科學領域中的一種基本演算法，AI 的成果現已被納入LLVM 標準C 庫Abseil 並開源。

這個成果有多重要？ AlphaDev 的主要作者之一，Google DeepMind 研究科學家Daniel J. Mankowitz 表示：「我們估計它發現的排序和雜湊演算法每天會在全世界被調用數萬億次。」

##AI 似乎從演算法層面加速了世界的運作。

這些演算法改進了LLVM libc 排序庫，對於較短的序列，排序庫的速度提高了70%，對於超過25 萬個元素的序列，速度也能提高約1.7%。 Google DeepMind 表示，這是十多年來排序庫這部分的第一次變更。看起來，現在 AI 不僅可以幫人寫程式碼，而且可以幫我們寫出更好的程式碼。

在最新的部落格中，新系統的作者們對 AlphaDev 進行了詳細介紹。

新的演算法將改變計算基礎

數位社會推動了對運算和能源日益增長的需求。在過去五十年裡，數位時代依靠硬體的改進來跟上需求。但是隨著微晶片接近其物理極限，改進在其上運行的程式碼變得至關重要。對於每天運行數萬億次的程式碼所包含的演算法來說，這尤其重要。

Google DeepMind 的這項研究就是因此產生的，相關論文已發表在《Nature》上，AlphaDev 是一個AI 系統，它使用強化學習來發現演算法，甚至超越了科學家和工程師們幾十年來打磨出來的成果。

#論文網址：https://www.nature.com/articles /s41586-023-06004-9

#整體來說，AlphaDev 發現了更快的排序演算法。雖然數十億人每天都在使用這些演算法，但沒有人意識到這個演算法還存在優化空間。排序演算法應用範圍廣泛，從線上搜尋結果、社群貼文排序，到電腦以及手機上的各種資料處理，都離不開排序演算法。利用 AI 產生更好的演算法將改變人類程式設計電腦的方式，對日益數位化的社會將產生重大影響。

透過在主要的C 庫中開源新排序演算法，全球數百萬開發人員和公司現在可以在雲端運算、線上購物和供應鏈管理等各行各業的人工智能應用中使用它。這是十多年來對排序庫的首次更改，也是透過強化學習設計的演算法首次被添加到該庫中。這將這視為使用人工智慧逐步優化世界程式碼的重要里程碑。

關於排序

排序演算法是一種依照特定順序排列某些任務的方法。例如，按字母先後順序排列三個字母，從大到小排列五個數字，或對數百萬筆記錄的資料庫進行排序。

這個演算法由來已久，並且得到了很好的演進。其中關於排序的最早一個例子可追溯到公元 2 世紀和 3 世紀，當時學者們在亞歷山大圖書館的書架上手工按字母順序排列了數千本書。隨著工業革命的到來，出現了可以幫助人們進行排序的機器，其中製表機使用打孔卡片存儲信息，這些卡片被用於收集美國 1890 年的人口普查結果。

隨著 1950 年代商用電腦的興起，最早用於排序演算法的電腦科學演算法開始發展。如今，在全球的程式碼庫中有許多不同的排序技術和演算法被用於處理大量的線上資料。

將一系列未排序的數字輸入到演算法中，輸出已排序的數字。

經過電腦科學家和程式設計師們幾十年的研究，目前的排序演算法已經非常高效，以至於很難再實現進一步的改進，這有點類似於試圖找到一種新的節省電力或更有效率的數學方法，而這些演算法也是電腦科學的基石。

探索新演算法：彙編指令

AlphaDev 從頭開始探索更快的演算法，而不是基於現有演算法之上，除此以外，AlphaDev 還能用於尋找大多數人所不涉足的領域：電腦彙編指令。

彙編指令可用來建立電腦執行的二進位程式碼。開發人員使用諸如 C 之類的高階語言編寫程式碼，但必須將其轉換為電腦能夠理解的“低階”彙編指令。

Google DeepMind 認為這個層次有許多改進的空間，而這些改進在更高階的程式語言中可能很難被發現。在這個層次上，電腦的儲存和操作更加靈活，這意味著存在更多潛在的改進可能性，這些改進可能對速度和能源使用產生更大的影響。

程式碼通常是用高階程式語言（如 C ）寫的。然後，編譯器將其轉換為低階 CPU 指令，稱為組譯指令。彙編器將彙編指令轉換為可執行的機器碼，以便電腦可以運作。

圖A：C 演算法範例，可對最多兩個元素進行排序；圖B：相應的彙編表示形式。

用AlphaGo 的方法尋找最佳演算法

AlphaDev 基於Google DeepMind 先前的一項成果：在圍棋、西洋棋和象棋等遊戲中打敗世界冠軍的強化學習模式AlphaZero。而 AlphaDev 則展示了這個模型如何從遊戲轉移到科學挑戰，以及從模擬到現實世界的應用。

為了訓練 AlphaDev 發現新的演算法，團隊將排序變成了一個單人的「組裝遊戲」。在每個回合中，AlphaDev 觀察它所產生的演算法和 CPU 中包含的訊息，然後透過選擇一條指令來加入演算法中來下一步棋。

彙編遊戲是非常困難的，因為 AlphaDev 必須在大量可能的指令組合中進行高效搜索，以找到一個可以排序的演算法，並且比當前的最佳演算法更快。指令的可能組合數量類似於宇宙中的粒子數量，或國際象棋（10^120 局）和圍棋（10^700 局）中可能的動作組合的數量，而一個錯誤的動作就可以使整個演算法失效。

#圖 A：組裝遊戲。玩家 AlphaDev 接收系統 st 的狀態作為輸入，並透過選擇彙編指令加入目前已產生的演算法來下棋。圖 B：獎勵計算。每次移動後，產生的演算法都會輸入測試輸入序列 —— 對於 sort3，這對應於三個元素序列的所有組合。然後演算法會產生一個輸出，將其與排序情況下排序序列的預期輸出進行比較。智能體根據演算法的正確性和延遲獲得獎勵。

在建立演算法時，對於每次的一條指令，AlphaDev 透過將演算法的輸出與預期結果進行比較來檢查它是否正確。對於排序演算法，這意味著無序數字進入，正確排序的數字出來。團隊會獎勵 AlphaDev 對數字的正確排序以及排序的速度和效率，然後 AlphaDev 透過發現正確、更快的程式來贏得比賽。

它發現了更快的排序演算法

AlphaDev 發現了新的排序演算法，這些演算法導致LLVM libc 排序庫得到改進：#對於較短的序列，排序庫的速度提高了70%，對於超過25 萬個元素的序列，速度提高了約1.7%。 

其中，Google DeepMind 團隊更專注於改進三到五個元素的短序列排序演算法。這些演算法是使用最廣泛的演算法之一，因為它們通常作為更大排序函數的一部分被多次調用，改進這些演算法可以提高對任意數量項目進行排序的整體速度。

為了讓新的排序演算法對人們更有用，團隊對演算法進行了逆向工程並將它們翻譯成C ，這是開發人員使用的最流行的程式語言之一。

目前，這些演算法已在LLVM libc 標準排序庫（https://reviews.llvm.org/D118029）中提供，並被全球數百萬開發人員和公司使用。

「交換與複製動作」，神之一手重現？

事實上，AlphaDev 不僅發現了更快的演算法，而且還發現了新的方法。它的排序演算法包含新的指令序列，每次應用時都會節省一條指令 —— 這顯然會產生巨大的影響，因為這些演算法每天都要使用數萬億次。他們把這些稱為「AlphaDev 交換和複製動作」。

這種新穎的方法讓人聯想到AlphaGo 的「第37 步」—— 當時這這種反直覺的下法讓圍觀者目瞪口呆，並導致李世石這位傳奇圍棋選手被打敗。透過交換和複製動作，AlphaDev 跳過了一個步驟，以一種看起來像錯誤但實際上是捷徑的方式連接項目。這表明 AlphaDev 有能力發掘出原創性的解決方案，並挑戰人類對如何改進電腦科學演算法的思考方式。

左圖：min (A,B,C) 原始的sort3 實作；右圖：AlphaDev交換移動－AlphaDev 發現你只需要min (A,B)。

#

左圖：在一個更大的排序演算法中使用max（B，min（A，C，D））的原始實現，用於排序八個元素；右圖：AlphaDev 發現，使用其複製動作時，只需要max（B，min（A，C））。

擴展能力測驗：從「排序」到「雜湊」

在發現更快的排序演算法後，團隊測試了AlphaDev 是否​​可以概括和改進不同的計算機科學演算法：哈希。 

雜湊是運算中用於檢索、儲存和壓縮資料的基本演算法。就像使用分類系統來定位某本書的圖書館員一樣，雜湊演算法可以幫助用戶知道他們正在尋找什麼以及在哪裡可以找到它。這些演算法會取得特定金鑰的資料（例如使用者名稱 “Jane Doe”）並對其進行雜湊處理 —— 這是將原始資料轉換為唯一字串（例如 1234ghfty）的過程。計算機使用此雜湊來快速檢索與密鑰相關的數據，而不是搜尋所有數據。

團隊將 AlphaDev 套用到資料結構中最常用的雜湊演算法之一，嘗試發現更快的演算法。當將其應用於 9-16 位元組範圍的雜湊函數時，AlphaDev 發現的演算法速度提高了 30%。

今年，AlphaDev 的新雜湊演算法已發佈到開源Abseil 庫中，可供全球數百萬開發人員使用，它現在大概每天被使用數萬億次。

開源地址：https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7dcd2dbaa69b2c654596d8024e

結語

Google DeepMind 透過最佳化和推出改進的排序和雜湊演算法，供世界各地的開發人員使用，AlphaDev 展示了其概括和發現具有現實影響的新演算法的能力。 AlphaDev 可被視為開發通用 AI 工具的一步，它可以幫助優化整個運算生態系統並解決其他造福社會的問題。

雖然在低階彙編指令空間中進行最佳化非常強大，但隨著演算法的成長， AlphaDev 仍存在局限性，團隊目前正在探索其直接在高階語言（如C ）中優化演算法的能力，這對開發人員來說更加有用。

AlphaDev 的發現，例如交換和複製動作，不僅表明它可以改進演算法，還可以找到新的解決方案。這些發現或許能夠激勵研究人員和開發人員創建可以進一步優化基礎演算法的技術和方法，以創建更強大和可持續的計算生態系統。

以上是AI重寫排序演算法，速度快70%：DeepMind AlphaDev革新運算基礎，每天呼叫萬億次的函式庫更新了的詳細內容。更多資訊請關注PHP中文網其他相關文章！