點(diǎn)擊參加51CTO網(wǎng)站內(nèi)容調(diào)查問(wèn)卷

編譯 | 王瑞平、言征

AlphaGo又有“小弟”加入了!

谷歌DeepMind把Alpha系列“卷”到了排序算法上，重磅推出AlphaDev。

它好比一種“開發(fā)秘法”，通過(guò)使用強(qiáng)化學(xué)習(xí)AI發(fā)現(xiàn)排序算法和散列算法，強(qiáng)行把人類程序員設(shè)計(jì)的算法分別提速約70%和30%。

研究成果一經(jīng)推出，瞬間點(diǎn)燃軟件圈！一下子，全球數(shù)以百萬(wàn)計(jì)的軟件運(yùn)行速度飆升，直接超越了科學(xué)家和工程師幾十年來(lái)的成果，十年未更新的LLVM標(biāo)準(zhǔn)C++庫(kù)都更新了。

（來(lái)源：Nature）

這也是繼谷歌兩AI部門合體后推出的顛覆性技術(shù)。論文以《使用深度強(qiáng)化學(xué)習(xí)模型發(fā)現(xiàn)更快排序算法》（Faster sorting algorithms discovered using deep reinforcement learning）為題發(fā)表于Nature。DeepMind計(jì)算機(jī)科學(xué)家Daniel Mankowitz為論文的第一作者。

1、演進(jìn)：排序算法的由來(lái)

排序是一種將許多項(xiàng)目按特定順序組織起來(lái)的方法，例如，按照字母順序排列三個(gè)字母，從最大到最小的順序排列五個(gè)數(shù)字或?qū)Π瑪?shù)百萬(wàn)條記錄的數(shù)據(jù)庫(kù)進(jìn)行排序。

排序法最早可追溯至二到三世紀(jì)，仍在不斷演進(jìn)。最初，學(xué)者們徒手將亞歷山大圖書館書架上的數(shù)千本書按字母順序進(jìn)行排序。

工業(yè)革命之后，人們發(fā)明了可自行分類的機(jī)器，即，將信息存儲(chǔ)在穿孔卡片上的制表機(jī)器中，用于收集1890年美國(guó)人口普查的結(jié)果。

20世紀(jì)50年代，商用計(jì)算機(jī)開始興起，也隨即產(chǎn)生了排序算法。將一系列未排序的數(shù)字輸入到排序算法中，它就能輸出排好順序的數(shù)字。

如今，在世界各地的代碼庫(kù)中，仍有許多不同的排序技術(shù)和算法被用于在線整理大量數(shù)據(jù)。      

這些排序算法經(jīng)過(guò)計(jì)算機(jī)科學(xué)家和程序員幾十年的研究開發(fā)，變得越來(lái)越高效。但是，對(duì)其進(jìn)一步改進(jìn)仍具有重大挑戰(zhàn)。

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

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

在這個(gè)實(shí)驗(yàn)中，AlphaDev是從零開始構(gòu)建新算法的，并不是根據(jù)以往算法構(gòu)建，屬于原創(chuàng)。在此過(guò)程中，它應(yīng)用了匯編代碼的中間語(yǔ)言。該語(yǔ)言更接近計(jì)算機(jī)二進(jìn)制指令，也更容易讓AlphaDev創(chuàng)造出高效算法。

具體來(lái)講，AlphaDev每次生成一個(gè)指令，然后測(cè)試其輸出正確與否，同時(shí)還在模型中設(shè)定要求生成最短算法。

當(dāng)被要求重新設(shè)計(jì)排序算法時(shí)，AlphaDev隨機(jī)生成比現(xiàn)有算法快70%的新排序算法，可同時(shí)將五個(gè)數(shù)據(jù)排序。在對(duì)25萬(wàn)個(gè)數(shù)據(jù)進(jìn)行排序時(shí)，它也比最好的算法快1.7%。

由于排序算法被廣泛用于各種常用軟件中，這項(xiàng)創(chuàng)新會(huì)對(duì)全球算法產(chǎn)生重大影響。DeepMind已將它們進(jìn)行開源，并加入Libc++常用代碼庫(kù)。

據(jù)DeepMind的研究者描述：“由于指令組合數(shù)量龐大，看似簡(jiǎn)單的研究過(guò)程難度極大。”

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

進(jìn)一步來(lái)講，AlphaDev是基于AlphaZero產(chǎn)生的更先進(jìn)模型。而AlphaZero此前是DeepMind的強(qiáng)化學(xué)習(xí)模型，曾在圍棋、國(guó)際象棋和其它棋類游戲中擊敗了世界冠軍。

通過(guò)此項(xiàng)實(shí)驗(yàn)，新模型AlphaDev發(fā)揮出從玩游戲轉(zhuǎn)移到解決科學(xué)問(wèn)題以及從實(shí)驗(yàn)?zāi)M轉(zhuǎn)移到現(xiàn)實(shí)世界應(yīng)用的獨(dú)特優(yōu)勢(shì)。

為訓(xùn)練AlphaDev發(fā)現(xiàn)新算法，研究者將排序模擬為單人“組裝游戲”。在每個(gè)游戲回合中，AlphaDev都能觀察到生成的算法和包含在CPU中的信息，然后選擇一條指令添加到算法中走出每一步棋。

論文中提到，匯編游戲非常困難，因?yàn)锳lphaDev必須能夠有效地搜索到大量可能的指令組合以獲取可以排序的算法。

指令組合數(shù)量類似于宇宙中粒子數(shù)量或國(guó)際象棋(10120局)和圍棋(10700局)中可能走法的組合數(shù)量，每個(gè)錯(cuò)誤的舉動(dòng)將會(huì)使整個(gè)算法失效。

然后，該模型輸出一個(gè)算法并將其與預(yù)期輸出比較，根據(jù)算法的正確性和延遲時(shí)間獎(jiǎng)勵(lì)代理。

在構(gòu)建算法時(shí)，每次輸入一個(gè)指令，AlphaDev通過(guò)比較輸出算法與預(yù)期結(jié)果檢查正確性（對(duì)于排序算法，這意味著輸入無(wú)序的數(shù)字后能夠輸出正確排序的數(shù)字）。

模型會(huì)獎(jiǎng)勵(lì)A(yù)lphaDev對(duì)數(shù)字的正確排序以及它的高效。最終AlphaDev通過(guò)發(fā)現(xiàn)更準(zhǔn)確的、更快的程序贏得了比賽。

4、算法創(chuàng)新：交換移動(dòng)和復(fù)制移動(dòng)指令序列

AlphaDev不僅生成了更快算法，還創(chuàng)新出兩種指令序列。

具體來(lái)講，它生成的排序算法包括交換移動(dòng)和復(fù)制移動(dòng)兩種新的指令序列，每次使用時(shí)都會(huì)保存一條指令。研究者稱之為“AlphaDev的交換移動(dòng)和復(fù)制移動(dòng)”。

這種新穎的方法讓人想起AlphaGo的“第37步”——“反直覺(jué)”下棋法，震驚了旁觀者并造成一位傳奇棋手的失敗。

通過(guò)交換移動(dòng)和復(fù)制移動(dòng)指令序列，AlphaDev跳過(guò)了一個(gè)步驟，以一種看起來(lái)像錯(cuò)誤但實(shí)際上是捷徑的方式完成目標(biāo)。這表明，AlphaDev有能力發(fā)現(xiàn)原始解決方案，并挑戰(zhàn)如何改進(jìn)計(jì)算機(jī)科學(xué)算法。

5、測(cè)試：推廣和改進(jìn)散列算法

在發(fā)現(xiàn)更快的排序算法后，研究者測(cè)試了AlphaDev是否可以推廣和改進(jìn)另一種計(jì)算機(jī)科學(xué)算法：散列算法。

散列算法是計(jì)算中的一種基本算法，用于檢索、存儲(chǔ)和壓縮數(shù)據(jù)。就像圖書管理員使用分類系統(tǒng)定位某本書一樣，散列算法幫助用戶知道他們要找的是什么以及在哪里可以找到它。

這些算法能夠獲取特定密鑰(例如，用戶名“Jane Doe”)的數(shù)據(jù)并對(duì)其進(jìn)行散列排序——將原始數(shù)據(jù)轉(zhuǎn)換為唯一字符串(例如，1234ghty)。

計(jì)算機(jī)使用該散列快速檢索與密鑰相關(guān)的數(shù)據(jù)，而不是搜索所有數(shù)據(jù)。

研究人員將AlphaDev應(yīng)用于數(shù)據(jù)結(jié)構(gòu)中最常用的散列算法之一以嘗試發(fā)現(xiàn)更快的算法。當(dāng)將其應(yīng)用于散列函數(shù)的9-16字節(jié)范圍時(shí)，AlphaDev生成的算法速度快了30%。

今年早些時(shí)候，AlphaDev生成的新散列算法曾被發(fā)布到開源的Abseil庫(kù)中，全世界數(shù)以百萬(wàn)計(jì)的開發(fā)人員都可以使用，估計(jì)它現(xiàn)在每天被使用數(shù)萬(wàn)億次。

6、蓄勢(shì)：邁出開發(fā)AGI的第一步  

通過(guò)優(yōu)化“排序和散列算法”，AlphaDev展示出生成不同實(shí)用新算法的能力。

這也是AlphaDev朝著開發(fā)通用人工智能（AGI）工具邁出的第一步，通過(guò)類似的AI工具還可以幫助優(yōu)化整個(gè)計(jì)算生態(tài)系統(tǒng)并解決其它有益于社會(huì)的問(wèn)題。

雖然在低級(jí)匯編指令空間中優(yōu)化算法的功能非常強(qiáng)大，但它也存在局限性。目前，團(tuán)隊(duì)也正在探索AlphaDev直接在高級(jí)語(yǔ)言(如，C++)中優(yōu)化算法的能力，這對(duì)開發(fā)人員更有用。

總之，希望這些新發(fā)現(xiàn)能夠激勵(lì)開發(fā)人員創(chuàng)造新技術(shù)和方法、進(jìn)一步優(yōu)化基本算法，創(chuàng)造更強(qiáng)大、更可持續(xù)的計(jì)算生態(tài)系統(tǒng)。

7、開源：AI優(yōu)化代碼的里程碑突破

此前，排序算法每天都會(huì)被使用數(shù)萬(wàn)億次。隨著計(jì)算需求的增長(zhǎng)，人們對(duì)算法的性能要求越來(lái)越高。雖然人類工程師已發(fā)現(xiàn)不同的排序算法，但經(jīng)過(guò)幾十年的優(yōu)化，很難再有突破，也滿足不了日益增長(zhǎng)的需求。

如今，AlphaDev發(fā)現(xiàn)了一種更快的排序算法，可對(duì)數(shù)據(jù)進(jìn)行排序。

新排序算法無(wú)所不能，既可應(yīng)用于對(duì)在線搜索結(jié)果和社交帖子進(jìn)行排名，也可在電腦和手機(jī)上處理數(shù)據(jù)。

值得慶賀的是，新排序算法已在主C++庫(kù)中開源。世界各地?cái)?shù)以百萬(wàn)的開發(fā)人員和公司目前可將其用于云計(jì)算、在線購(gòu)物、供應(yīng)鏈管理等。

總之，使用人工智能工具優(yōu)化算法將徹底改變傳統(tǒng)編程方式。這是十幾年來(lái)第一次對(duì)排序庫(kù)進(jìn)行更改，第一次將強(qiáng)化學(xué)習(xí)模型設(shè)計(jì)出的算法添加到排序庫(kù)中，因此成為了使用人工智能優(yōu)化代碼的里程碑式突破。

8、用戶：可能只是噱頭 

對(duì)于該項(xiàng)研究成果用戶褒貶不一，Twitter上贊美的聲音居多：

“這太棒了！在程序員早期就學(xué)會(huì)的基本排序任務(wù)基礎(chǔ)上，速度提高了70%?？吹嚼肁I在我們都依賴的算法和庫(kù)中進(jìn)行重大加速，真是令人興奮”。

“很快，普通人就可以成為高級(jí)程序員”。

“有趣的方法，從裝配級(jí)別開始優(yōu)化”！

但是，也有的程序員認(rèn)為這只是個(gè)噱頭，DeepMind夸大了該算法的功能。

首先就是從效率的角度，它只統(tǒng)計(jì)了算法的延遲，而非真正改變了時(shí)間復(fù)雜度。

而且，它并沒(méi)有真正改變排序，這種操作常見(jiàn)于各種其它代碼庫(kù)。

參考資料：

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