MIT新研究：43%算法改進速度超摩爾定律，解決超大規(guī)模問題，算法比硬件更有用
這是MIT研究1137篇論文后得到的結(jié)果
博雯 發(fā)自 凹非寺
量子位 報道 | 公眾號 QbitAI
軟件算法對計算速度的提升有多大？
MIT最新研究說：超過4成算法對性能的改進，已經(jīng)超過了硬件的摩爾定律。
對于中等規(guī)模的問題，30%-43%的算法的改進比硬件進步更能提升性能。
當(dāng)問題數(shù)據(jù)增加到數(shù)億規(guī)模時，算法改進變得比硬件改進/摩爾定律更重要。
這就是MIT的兩位科學(xué)家對來自57本教科書，超過1137篇研究論文的數(shù)據(jù)進行分析后得到的結(jié)論。
不僅如此，他們還全面敘述了現(xiàn)有以及歷史上的算法何時被發(fā)現(xiàn)、如何改進、以及改進的規(guī)模。
14%的算法改進率超過1000%
研究者通過分析QS排名中前20的計算機名校所用的課件，總結(jié)出11個算法子領(lǐng)域：
組合學(xué)、統(tǒng)計學(xué)/機器學(xué)習(xí)、密碼學(xué)、數(shù)值分析、數(shù)據(jù)庫、操作系統(tǒng)、計算機網(wǎng)絡(luò)、機器人學(xué)、信號處理、計算機圖形/圖像處理、生物信息學(xué)。
通過分析子領(lǐng)域中的算法教材、學(xué)術(shù)期刊、已發(fā)表論文等信息，研究者劃分出了113個算法家族，平均每個家族8個算法。
他們首先統(tǒng)計了從1940年到現(xiàn)在，各種算法的最初提出時間：
并且根據(jù)這些算法最初被提出時的時間復(fù)雜度進行了歸納?？梢钥吹剑渲?1%的算法屬于指數(shù)復(fù)雜度類別：
在時間復(fù)雜度的改進上，對于n=100萬的問題規(guī)模，一些算法比硬件或摩爾定律的改進率更高：
將這一分析拓展到110個算法家族上時，可以看到，對于中等規(guī)模（n=1000）的問題來說，只有18%的算法改進率快于硬件。
但當(dāng)問題規(guī)模來到了百萬、億、甚至萬億級別時，算法的改進速度就超過了硬件性能。
甚至有14%的算法家族的改進率超過1000%，遠超硬件改進所帶來的性能提升。
作者介紹
論文一作Yash Sherry本科畢業(yè)于印度德里大學(xué)計算機科學(xué)專業(yè)，現(xiàn)在是MIT斯隆商學(xué)院的一位研究員，工作重點是跟蹤算法的改進及其對IT公司經(jīng)濟的影響。
另一位Neil Thompson是麻省理工大學(xué)CSAIL（計算機科學(xué)和人工智能實驗室）的科學(xué)家，也是哈佛大學(xué)創(chuàng)新科學(xué)實驗室的客座教授。
論文：
https://ieeexplore.ieee.org/document/9540991
參考鏈接：
https://news.mit.edu/2021/how-quickly-do-algorithms-improve-0920
- 有道智能學(xué)習(xí)燈發(fā)布，通過“桌面學(xué)習(xí)分析引擎”實現(xiàn)全球最快指尖查詞2022-04-08
- 科學(xué)證明：狗勾真的懂你有多累，聽到聲音0.25秒后就知道你是誰，對人比對狗更親近2022-04-14
- 在M1芯片上跑原生Linux：編譯速度比macOS還快40%2022-04-05
- 小學(xué)生們在B站講算法，網(wǎng)友：我只會阿巴阿巴2022-03-28
相關(guān)閱讀
商湯聯(lián)合創(chuàng)始人楊帆：人工智能產(chǎn)業(yè)正在面臨一個“幸福的煩惱” | MEET2022
AI算法正在從“手工作坊”轉(zhuǎn)變?yōu)椤凹辛慨a(chǎn)”
站芯片封面.png)
