它發(fā)現(xiàn)了更快的排序算法，速度快 70%

「通過(guò)交換和復(fù)制移動(dòng)，AlphaDev 跳過(guò)了一個(gè)步驟，以一種看似錯(cuò)誤，但實(shí)際上是捷徑的方式連接項(xiàng)目?！惯@種前所未見(jiàn)、違反直覺(jué)的思想不禁讓人回憶起 2016 年那個(gè)春天。

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

今天凌晨，Google DeepMind CEO 哈薩比斯的兩句話引爆了計(jì)算機(jī)領(lǐng)域：「AlphaDev 發(fā)現(xiàn)了一種全新且更快的排序算法，我們已將其開(kāi)源到主要 C++ 庫(kù)中供開(kāi)發(fā)人員使用。這只是 AI 提升代碼效率進(jìn)步的開(kāi)始?！?/p>

這一次，Google DeepMind 的全新強(qiáng)化學(xué)習(xí)系統(tǒng) AlphaDev 發(fā)現(xiàn)了一種比以往更快的哈希算法，這是計(jì)算機(jī)科學(xué)領(lǐng)域中的一種基本算法，AI 的成果現(xiàn)已被納入 LLVM 標(biāo)準(zhǔn) C++ 庫(kù) Abseil 并開(kāi)源。

這個(gè)成果有多重要？AlphaDev 的主要作者之一，Google DeepMind 研究科學(xué)家 Daniel J. Mankowitz 表示：「我們估計(jì)它發(fā)現(xiàn)的排序和哈希算法每天會(huì)在全世界被調(diào)用數(shù)萬(wàn)億次?！?/p>

AI 似乎從算法層面加速了世界的運(yùn)轉(zhuǎn)。

這些算法改進(jìn)了 LLVM libc++ 排序庫(kù)，對(duì)于較短的序列，排序庫(kù)的速度提高了 70%，對(duì)于超過(guò) 25 萬(wàn)個(gè)元素的序列，速度也能提高約 1.7%。Google DeepMind 表示，這是十多年來(lái)排序庫(kù)這部分的第一次變化?？雌饋?lái)，現(xiàn)在 AI 不僅可以幫人寫(xiě)代碼，而且可以幫我們寫(xiě)出更好的代碼。

在最新的博客中，新系統(tǒng)的作者們對(duì) AlphaDev 進(jìn)行了詳細(xì)介紹。

新的算法將改變計(jì)算基礎(chǔ)

數(shù)字社會(huì)推動(dòng)了對(duì)計(jì)算和能源日益增長(zhǎng)的需求。過(guò)去五十年里，數(shù)字時(shí)代依靠硬件的改進(jìn)來(lái)跟上需求。但是隨著微芯片接近其物理極限，改進(jìn)在其上運(yùn)行的代碼變得至關(guān)重要。對(duì)于每天運(yùn)行數(shù)萬(wàn)億次的代碼所包含的算法來(lái)說(shuō)，這尤其重要。

Google DeepMind 的這項(xiàng)研究就是因此產(chǎn)生的，相關(guān)論文已發(fā)表在《Nature》上，AlphaDev 是一個(gè) AI 系統(tǒng)，它使用強(qiáng)化學(xué)習(xí)來(lái)發(fā)現(xiàn)算法，甚至超越了科學(xué)家和工程師們幾十年來(lái)打磨出來(lái)的成果。

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

總體來(lái)說(shuō)，AlphaDev 發(fā)現(xiàn)了一種更快的排序算法。雖然數(shù)十億人每天都在使用這些算法，但卻沒(méi)有人意識(shí)到這一算法還存在優(yōu)化空間。排序算法應(yīng)用范圍廣泛，從在線搜索結(jié)果、社交帖子排序，到計(jì)算機(jī)以及手機(jī)上的各種數(shù)據(jù)處理，都離不開(kāi)排序算法。利用 AI 生成更好的算法將改變?nèi)祟惥幊逃?jì)算機(jī)的方式，對(duì)日益數(shù)字化的社會(huì)將產(chǎn)生重大影響。

通過(guò)在主要的 C++ 庫(kù)中開(kāi)源新排序算法，全球數(shù)百萬(wàn)開(kāi)發(fā)人員和公司現(xiàn)在可以在云計(jì)算、在線購(gòu)物和供應(yīng)鏈管理等各行各業(yè)的人工智能應(yīng)用中使用它。這是十多年來(lái)對(duì)排序庫(kù)的首次更改，也是通過(guò)強(qiáng)化學(xué)習(xí)設(shè)計(jì)的算法首次被添加到該庫(kù)中。這將這視為使用人工智能逐步優(yōu)化世界代碼的重要里程碑。

關(guān)于排序

排序算法是一種按照特定順序?qū)δ承┤蝿?wù)進(jìn)行排列的方法。例如，按字母先后順序排列三個(gè)字母，從大到小排列五個(gè)數(shù)字，或者對(duì)數(shù)百萬(wàn)條記錄的數(shù)據(jù)庫(kù)進(jìn)行排序。

這種算法由來(lái)已久，并得到了很好的演進(jìn)。其中關(guān)于排序的最早一個(gè)示例可追溯到公元 2 世紀(jì)和 3 世紀(jì)，當(dāng)時(shí)學(xué)者們?cè)趤啔v山大圖書(shū)館的書(shū)架上手工按字母順序排列了數(shù)千本書(shū)。隨著工業(yè)革命的到來(lái)，出現(xiàn)了可以幫助人們進(jìn)行排序的機(jī)器，其中制表機(jī)使用打孔卡片存儲(chǔ)信息，這些卡片被用于收集美國(guó) 1890 年的人口普查結(jié)果。

隨著上世紀(jì) 50 年代商用計(jì)算機(jī)的興起，最早用于排序算法的計(jì)算機(jī)科學(xué)算法開(kāi)始發(fā)展。如今，在全球的代碼庫(kù)中有許多不同的排序技術(shù)和算法被用于處理海量的在線數(shù)據(jù)。

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

經(jīng)過(guò)計(jì)算機(jī)科學(xué)家和程序員們幾十年的研究，目前的排序算法已經(jīng)非常高效，以至于很難再實(shí)現(xiàn)進(jìn)一步的改進(jìn)，這有點(diǎn)類似于試圖找到一種新的節(jié)省電力或更高效的數(shù)學(xué)方法，而這些算法也是計(jì)算機(jī)科學(xué)的基石。

探索新算法：匯編指令

AlphaDev 從頭開(kāi)始探索更快的算法，而不是基于現(xiàn)有算法之上，除此以外，AlphaDev 還能用于尋找大多數(shù)人所不涉足的領(lǐng)域：計(jì)算機(jī)匯編指令。

匯編指令可用于創(chuàng)建計(jì)算機(jī)執(zhí)行的二進(jìn)制代碼。開(kāi)發(fā)人員使用諸如 C++ 之類的高級(jí)語(yǔ)言編寫(xiě)代碼，但必須將其轉(zhuǎn)換為計(jì)算機(jī)能夠理解的「低級(jí)」匯編指令。

Google DeepMind 認(rèn)為這個(gè)層次存在許多改進(jìn)的空間，而這些改進(jìn)在更高級(jí)的編程語(yǔ)言中可能很難被發(fā)現(xiàn)。在這個(gè)層次上，計(jì)算機(jī)的存儲(chǔ)和操作更加靈活，這意味著存在更多潛在的改進(jìn)可能性，這些改進(jìn)可能對(duì)速度和能源使用產(chǎn)生更大的影響。

代碼通常是用高級(jí)編程語(yǔ)言（如 C++）編寫(xiě)的。然后，編譯器將其轉(zhuǎn)換為低級(jí) CPU 指令，稱為匯編指令。匯編器將匯編指令轉(zhuǎn)換為可執(zhí)行的機(jī)器碼，以便計(jì)算機(jī)可以運(yùn)行。

圖 A：C++ 算法示例，該算法可對(duì)最多兩個(gè)元素進(jìn)行排序；圖 B：相應(yīng)的匯編表示形式。

用 AlphaGo 的方法尋找最佳算法

AlphaDev 基于 Google DeepMind 此前的一項(xiàng)成果：在圍棋、國(guó)際象棋和象棋等游戲中打敗世界冠軍的強(qiáng)化學(xué)習(xí)模型 AlphaZero。而 AlphaDev 展示了這個(gè)模型如何從游戲轉(zhuǎn)移到科學(xué)挑戰(zhàn)，以及從模擬到現(xiàn)實(shí)世界的應(yīng)用。

為了訓(xùn)練 AlphaDev 發(fā)現(xiàn)新的算法，團(tuán)隊(duì)將排序變成了一個(gè)單人的「組裝游戲」。在每個(gè)回合中，AlphaDev 觀察它所產(chǎn)生的算法和 CPU 中包含的信息，然后通過(guò)選擇一條指令添加到算法中來(lái)下一步棋。

匯編游戲是非常困難的，因?yàn)?AlphaDev 必須在大量可能的指令組合中進(jìn)行高效搜索，以找到一個(gè)可以排序的算法，并且比當(dāng)前的最佳算法更快。指令的可能組合數(shù)量類似于宇宙中的粒子數(shù)量，或者國(guó)際象棋（10^120 局）和圍棋（10^700 局）中可能的動(dòng)作組合的數(shù)量，而一個(gè)錯(cuò)誤的動(dòng)作就可以使整個(gè)算法失效。

圖 A：組裝游戲。玩家 AlphaDev 接收系統(tǒng) st 的狀態(tài)作為輸入，并通過(guò)選擇一條匯編指令添加到目前已生成的算法中來(lái)下棋。圖 B：獎(jiǎng)勵(lì)計(jì)算。每次移動(dòng)后，生成的算法都會(huì)輸入測(cè)試輸入序列 —— 對(duì)于 sort3，這對(duì)應(yīng)于三個(gè)元素序列的所有組合。該算法然后生成一個(gè)輸出，將其與排序情況下排序序列的預(yù)期輸出進(jìn)行比較。智能體根據(jù)算法的正確性和延遲獲得獎(jiǎng)勵(lì)。

在構(gòu)建算法時(shí)，對(duì)于每次的一條指令，AlphaDev 通過(guò)將算法的輸出與預(yù)期結(jié)果進(jìn)行比較來(lái)檢查它是否正確。對(duì)于排序算法，這意味著無(wú)序數(shù)字進(jìn)入，正確排序的數(shù)字出來(lái)。團(tuán)隊(duì)會(huì)獎(jiǎng)勵(lì) AlphaDev 對(duì)數(shù)字的正確排序以及排序的速度和效率，然后 AlphaDev 通過(guò)發(fā)現(xiàn)正確、更快的程序來(lái)贏得比賽。

它發(fā)現(xiàn)了更快的排序算法

AlphaDev 發(fā)現(xiàn)了新的排序算法，這些算法導(dǎo)致 LLVM libc++ 排序庫(kù)得到改進(jìn)：對(duì)于較短的序列，排序庫(kù)的速度提高了 70%，對(duì)于超過(guò) 25 萬(wàn)個(gè)元素的序列，速度提高了約 1.7%。

其中，Google DeepMind 團(tuán)隊(duì)更專注于改進(jìn)三到五個(gè)元素的短序列排序算法。這些算法是使用最廣泛的算法之一，因?yàn)樗鼈兺ǔＷ鳛楦笈判蚝瘮?shù)的一部分被多次調(diào)用，改進(jìn)這些算法可以提高對(duì)任意數(shù)量項(xiàng)目進(jìn)行排序的整體速度。

為了讓新的排序算法對(duì)人們更有用，團(tuán)隊(duì)對(duì)算法進(jìn)行了逆向工程并將它們翻譯成 C++，這是開(kāi)發(fā)人員使用的最流行的編程語(yǔ)言之一。

目前，這些算法已在 LLVM libc++ 標(biāo)準(zhǔn)排序庫(kù)（https://reviews.llvm.org/D118029）中提供，被全球數(shù)百萬(wàn)開(kāi)發(fā)人員和公司使用。

「交換和復(fù)制動(dòng)作」，神之一手重現(xiàn)？

事實(shí)上，AlphaDev 不僅發(fā)現(xiàn)了更快的算法，而且還發(fā)現(xiàn)了新的方法。它的排序算法包含新的指令序列，每次應(yīng)用時(shí)都會(huì)節(jié)省一條指令 —— 這顯然會(huì)產(chǎn)生巨大的影響，因?yàn)檫@些算法每天都要使用數(shù)萬(wàn)億次。他們把這些稱為「AlphaDev 交換和復(fù)制動(dòng)作」。

這種新穎的方法讓人聯(lián)想到 AlphaGo 的「第 37 步」—— 當(dāng)時(shí)這這種反直覺(jué)的下法讓圍觀者目瞪口呆，并導(dǎo)致李世石這位傳奇圍棋選手被打敗。通過(guò)交換和復(fù)制動(dòng)作，AlphaDev 跳過(guò)了一個(gè)步驟，以一種看起來(lái)像錯(cuò)誤但實(shí)際上是捷徑的方式連接項(xiàng)目。這表明 AlphaDev 有能力發(fā)掘出原創(chuàng)性的解決方案，并挑戰(zhàn)人類對(duì)如何改進(jìn)計(jì)算機(jī)科學(xué)算法的思考方式。

左圖：min （A，B，C） 原始的 sort3 實(shí)現(xiàn)；右圖：AlphaDev 交換移動(dòng) ——AlphaDev 發(fā)現(xiàn)你只需要 min （A，B）。

左圖：在一個(gè)更大的排序算法中使用 max（B，min（A，C，D））的原始實(shí)現(xiàn)，用于排序八個(gè)元素；右圖：AlphaDev 發(fā)現(xiàn)，使用其復(fù)制動(dòng)作時(shí)，只需要 max（B，min（A，C））。

擴(kuò)展能力測(cè)驗(yàn)：從「排序」到「哈?！?/p>

在發(fā)現(xiàn)更快的排序算法后，團(tuán)隊(duì)測(cè)試了 AlphaDev 是否可以概括和改進(jìn)不同的計(jì)算機(jī)科學(xué)算法：哈希。

哈希是計(jì)算中用于檢索、存儲(chǔ)和壓縮數(shù)據(jù)的基本算法。就像使用分類系統(tǒng)來(lái)定位某本書(shū)的圖書(shū)管理員一樣，哈希算法可以幫助用戶知道他們正在尋找什么以及在哪里可以找到它。這些算法獲取特定密鑰的數(shù)據(jù)（例如用戶名 “Jane Doe”）并對(duì)其進(jìn)行哈希處理 —— 這是一個(gè)將原始數(shù)據(jù)轉(zhuǎn)換為唯一字符串（例如 1234ghfty）的過(guò)程。計(jì)算機(jī)使用此哈希來(lái)快速檢索與密鑰相關(guān)的數(shù)據(jù)，而不是搜索所有數(shù)據(jù)。

團(tuán)隊(duì)將 AlphaDev 應(yīng)用于數(shù)據(jù)結(jié)構(gòu)中最常用的哈希算法之一，嘗試發(fā)現(xiàn)更快的算法。當(dāng)將其應(yīng)用于 9-16 字節(jié)范圍的哈希函數(shù)時(shí)，AlphaDev 發(fā)現(xiàn)的算法速度提高了 30%。

今年，AlphaDev 的新哈希算法已被發(fā)布到開(kāi)源 Abseil 庫(kù)中，可供全球數(shù)百萬(wàn)開(kāi)發(fā)人員使用，它現(xiàn)在大概每天被使用數(shù)萬(wàn)億次。

開(kāi)源地址：https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7dcd2dbaa69b2c654596d8024e

結(jié)語(yǔ)

Google DeepMind 通過(guò)優(yōu)化和推出改進(jìn)的排序和哈希算法，供世界各地的開(kāi)發(fā)人員使用，AlphaDev 展示了其概括和發(fā)現(xiàn)具有現(xiàn)實(shí)影響的新算法的能力。AlphaDev 可被視為開(kāi)發(fā)通用 AI 工具的一步，它可以幫助優(yōu)化整個(gè)計(jì)算生態(tài)系統(tǒng)并解決其他造福社會(huì)的問(wèn)題。

雖然在低級(jí)匯編指令空間中進(jìn)行優(yōu)化非常強(qiáng)大，但隨著算法的增長(zhǎng)， AlphaDev 仍存在局限性，團(tuán)隊(duì)目前正在探索其直接在高級(jí)語(yǔ)言（如 C++）中優(yōu)化算法的能力，這對(duì)開(kāi)發(fā)人員來(lái)說(shuō)更加有用。

AlphaDev 的發(fā)現(xiàn)，例如交換和復(fù)制動(dòng)作，不僅表明它可以改進(jìn)算法，還可以找到新的解決方案。這些發(fā)現(xiàn)或許能夠激勵(lì)研究人員和開(kāi)發(fā)人員創(chuàng)建可以進(jìn)一步優(yōu)化基礎(chǔ)算法的技術(shù)和方法，以創(chuàng)建更強(qiáng)大和可持續(xù)的計(jì)算生態(tài)系統(tǒng)。