整理 | 核子可樂，褚杏娟
接觸過基礎電腦科學課程的朋友們，肯定都曾親自動手設計排序演算法——也就是藉助程式碼將無序列表中的各個條目按升序或降序方式重新排列。這是個有趣的挑戰，可行的操作方法也多元。人們曾投入大量時間探索如何更有效率地完成排序任務。
作為一項基礎操作，大多數程式語言的標準庫中都內建有排序演算法。世界各地的程式碼庫中使用了許多不同的排序技術和演算法來在線組織大量數據，但至少就與 LLVM 編譯器配套使用的 C 庫而言，排序程式碼已經有十多年沒有任何變化了。
近日，Google DeepMind AI 小組如今開發出一種強化學習工具 AlphaDev，能夠在無需透過人類程式碼範例做預訓練的情況下，開發出極限優化的演算法。如今，這些演算法已經整合到 LLVM 標準 C 排序庫中，這是十多年來排序庫部分第一次發生變化，也是第一次將透過強化學習設計的演算法添加到該庫中。
把程式設計過程視為「遊戲」#
##DeepMind系統通常能夠發現人類從未想過的解決問題的方法，因為它不需要預先接觸任何人類遊戲策略。 DeepMind 學習經驗時完全依賴自我對抗，因此在某些情況下會形成可被人類利用的盲點。這種方法跟程式設計其實非常相似。大型語言模型能夠編寫有效的程式碼，因為它們已見過大量人類程式碼範例。但也因為如此，語言模型很難產出人類之前沒做過的東西。如果我們希望對普遍存在的現有演算法（例如排序函數）做進一步優化，那麼繼續依賴現有人類程式碼將很難突破固有思路的束縛。那麼，如何才能讓 AI 找到真正的新方向呢？
DeepMind研究人員使用了類似於國際象棋和圍棋的方法來優化程式碼任務，將其轉化為單人的「拼圖遊戲」。 AlphaDev 系統開發出一種 x86 彙編演算法，將程式碼的運行延遲視為一個分數，在努力將該分數最小化的同時確保程式碼能夠順暢跑通。 AlphaDev逐漸掌握了撰寫高效、簡潔程式碼的技巧，這得益於強化學習的應用。
AlphaDev 基於 AlphaZero。 DeepMind is well-known for developing AI software that can learn game rules on its own.。這一路思維被證實非常有效，並成功解決了許多遊戲難題，如西洋棋、圍棋和《星海爭霸》等。雖然具體細節因所玩遊戲而異，但 DeepMind 軟體確實能在重複遊玩中不斷學習，持續探索能令得分最大化的辦法。
AlphaDev 的兩個核心元件是學習演算法和表示函數。
使用 DRL 和隨機搜尋最佳化演算法結合來進行組裝遊戲，是 AlphaDev 學習演算法的一種方法。 AlphaDev 中的主要學習演算法是 AlphaZero 33 的擴展，AlphaZero 33 是一種著名的 DRL 演算法，其中訓練神經網路以指導搜尋完成遊戲。
此函數用於監控程式碼開發時的綜合效能，涵蓋了演算法一般結構，以及對 x86 暫存器和記憶體的使用。該系統將逐步引入彙編指令，在使用遊戲系統借鑒的蒙特卡羅樹搜尋方法進行選擇時獨立添加。樹狀結構允許系統快速將搜尋範圍縮小至包含大量潛在指令的有限區域，而蒙特卡羅方法則以一定程度的隨機性從這個分支區域內選擇具體指令。請注意，這裡所指的「指令」是選定特定暫存器等操作以建立有效且完整的組件。 ）
接著，系統會對彙編程式碼的延遲和有效狀態進行評估，並給出分數，並將其與上一次得分進行比較。透過強化學習，系統能夠記錄樹狀結構中不同分支的工作訊息，以用於給定的程序狀態。在隨著時間的推移，系統會逐漸熟悉如何以最高得分（代表最低延遲）來贏得遊戲（成功完成排序）。 The primary representation function of AlphaDev is based on Transformers.。
為了訓練 AlphaDev 發現新演算法，AlphaDev 在每輪中都會觀察它生成的演算法和中央處理器 (CPU) 中包含的信息，然後透過選擇要添加到演算法中的指令完成遊戲。 AlphaDev 必須有效地搜尋大量可能的指令組合，以找到可以排序的演算法，並且還要比目前最好的演算法更快，同時代理模型可以根據演算法的正確性和延遲獲得獎勵。
最終，AlphaDev 發現了新的排序演算法，這些演算法可以讓LLVM libc 排序庫得到改進：對於較短的序列，排序庫的速度提高了70%；對於超過250,000 個元素的序列，速度提高了約1.7%。
具體而言，此演算法的創新主要在於兩種指令序列：AlphaDev Swap Move（交換移動）和AlphaDev Copy Move（複製移動），透過這兩個指令，AlphaDev 跳過了一個步驟，以一種看似錯誤但實際上是捷徑的方式連接項目。
左圖：帶有 min(A,B,C) 的原始 sort3 實作。
右圖：AlphaDev Swap Move - AlphaDev 發現你只需要 min(A,B)。
左：max (B, min (A, C)) 的原始實作用於對八個元素進行排序的更大排序演算法。
右：AlphaDev 發現在使用其複製移動時只需要 max (B, min (A, C))。
這套系統的主要優點在於，其訓練過程不借助任何程式碼範例。相反，系統會自主產生程式碼範例，然後對其做出評估。過程當中，它也逐漸掌握了關於有效排序的指令組合資訊。
從排序到散列
在發現更快的排序演算法後，DeepMind 測試了 AlphaDev 是否可以概括和改進不同的電腦科學演算法：雜湊。
哈希是計算中用於檢索、儲存和壓縮資料的基本演算法。就像使用分類系統來定位某本書的圖書館員一樣，雜湊演算法可以幫助使用者知道他們正在尋找什麼以及在哪裡可以找到它。這些演算法會取得特定金鑰的資料（例如使用者名稱「Jane Doe」）並對其進行雜湊處理——這是將原始資料轉換為唯一字串（例如 1234ghfty）的過程。此雜湊演算法用於快速檢索與金鑰相關的數據，避免了搜尋全部數據的過程。
DeepMind 將 AlphaDev 應用於資料結構中最常用的雜湊演算法之一，以嘗試發現更快的演算法。 AlphaDev發現，在雜湊函數使用9-16位元組範圍內的資料時，演算法的速度提高了30%。
今年，AlphaDev 的新哈希演算法被發佈到開源 Abseil 庫中，可供全球數百萬開發人員使用，該庫現在每天被數萬億次使用。
實際可用的程式碼
複雜程式中的排序機制能夠處理大量任意條目的集合。但在標準庫層面來看，這種能力源自於一系列高度限定的具體函數。這些函數各自只能處理一種或幾種情況。例如，某些單獨演算法只能對 3、4 或 5 個條目做排序。我們可以使用一組函數對任意數量的條目進行排序，但是每次函數呼叫最多只能對4個條目排序。
AlphaDev has been implemented by DeepMind on each function, but its actual operating methods differ significantly.。可以編寫沒有分支語句的程式碼來處理特定數量條目的函數，也就是根據變數狀態執行不同的程式碼。因此程式碼效能往往與所涉及的指令數量成反比。
AlphaDev 已經成功將 sort-3、sort-5 和 sort-8 的指令數量各減一，在 sort-6 和 sort-7 中的指令削減量甚至更多。只有 sort-4 上沒能找到改進現有程式碼的方法。實際系統中重複執行測試表明，較少的指令確實提高了效能。
要對可變數量的條目進行排序，就需要在程式碼中包含分支語句，而不同處理器專門處理這些分支的元件數量也不同。
研究人員在對這種情況進行評估時，使用了100台不同的計算設備。 AlphaDev 在這類場景下也找到了進一步榨取效能的方法，以下我們以一次最多排序 4 個條目的函數為例，看看它到底是怎麼操作的。
在 C 函式庫的現有實作中，程式碼需要進行一系列測試來確認具體需要對多少個條目做排序，再根據條目數量呼叫對應的排序函數。
而 AlphaDev 修改後的程式碼則採取更「神奇」的想法：它先測試是不是 2 個條目，如果是則呼叫對應函數立即做排序。如果數量大於 2 個，則程式碼會先對前 3 個條目做排序。這樣如果確實只有 3 個條目，則傳回排序結果。由於實際上有 4 個條目要做排序，所以 AlphaDev 會運行專門程式碼，以非常有效率的方式將第 4 個條目插入到前 3 個已經排序完成的條目中的適當位置。
這種辦法聽起來有點怪異，但事實證明其效能確實始終優於現有程式碼。
由於 AlphaDev 確實產生了更有效率的程式碼，所以研究團隊打算把這些成果重新合併到 LLVM 標準 C 函式庫中。但問題是這些程式碼為彙編格式，而非 C 。因此，他們需要進行逆向計算，以找出產生相同組件的 C 程式碼。
這句話的重寫版本：現在，這部分程式碼已經被整合入 LLVM 工具鏈，並進行了近十年以來的首次更新。根據研究人員的估計，AlphaDev每天產生的新代碼被執行數萬億次。
結束語
這真是太好了！我們程式設計師早在很早以前就學會了這種基本的排序任務，但現在我們的速度提高了 70%。我們都依賴的演算法和函式庫中的 AI 提供了重大的加速，讓人感到非常興奮。 」有開發者對Google DeepMind 的成果表示振奮。
但也有開發者不買單：「相當令人失望…1.7% 的改善？5 個元素的序列70%？可能是最不受歡迎、最不切實際的應用研究…」也有開發者表示：「說發現了新演算法是不是有點誤導人？似乎更像是演算法優化。無論如何這仍然很酷。」
參考連結：
#https://arstechnica.com/science/2023/06/googles-deepmind-develops-a-system-that-writes-efficient-algorithms/
https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms
深度：為什麼中國資料庫領域沒有出現像Snowflake這樣的巨人？
十七年來奇葩大崩壞！為不讓OpenAI和谷歌白拿數據，Reddit 收取巨額API 費用還誹謗開發者，社區爆發大規模抗議
「偷」代碼建起公司、學歷造假、6天拿下1億美元卻拖欠工資，這位AI獨角獸CEO屢遭質疑後親自回應了
以上是谷歌借AI打破十年排序演算法封印，每天被執行數萬億次，網友卻說是最不切實際的研究？的詳細內容。更多資訊請關注PHP中文網其他相關文章！
