?作者?|?杜偉、陳萍

來源?|?機器之心

算法的改進到底能帶來多大的益處？來自 MIT 的研究者撰寫了有史以來第一次對算法進展研究的綜合分析論文。在綜合研究后，他們發現對于大型計算問題，43% 的算法改進等于或大于摩爾定律帶來的益處；在 14% 的問題中，算法對性能的改進大大超過了硬件改進帶來的益處。

算法決定了計算機使用哪種計算方法來解決問題，是計算機科學的核心支柱之一。隨著算法的改進，研究人員可以探索更難的問題并開創新的領域和技術。對于算法的發展速度，人們已經做出了大膽的斷言。例如 PCAST（一個為美國總統提供建議的資深科學家團體）曾在 2010 年寫道，在許多領域，由于算法的改進所帶來的性能提升，遠遠超過了由于處理器速度的提高所帶來的顯著性能提升。然而，這一結論是基于線性求解器的進展數據支持的，這只是一個單一例子。一般來說，由于不能保證線性求解器代表算法，因此我們不清楚應該對 PCAST 等結論進行多大范圍的解釋。?

關于算法與計算機的關系，有人說算法有點像計算機的父母。它們告訴計算機如何理解信息，反過來，算法又可以從計算機中獲得有用的東西。算法效率越高，計算機要做的工作就越少。對于計算機硬件的技術改進，以及備受爭議的摩爾定律是否到達極限，其實，計算機性能只是問題的一方面。另外，算法也在不斷的改進，相應的，所需的計算能力變得更少。雖然算法效率問題可能不太受到太多關注，但你肯定會注意到這種情況，搜索引擎突然變快。

來自 MIT 計算機科學與人工智能實驗室 (CSAIL) 的科學家提出疑問：算法改進的速度到底有多快？

為此，他們撰寫了有史以來第一次對算法進展研究的綜合分析，文章題目為《 How Fast Do Algorithms Improve? 》，并發表在 IEEE Proceedings 上。?

論文鏈接：

https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9540991

這項研究使我們能夠系統地查看算法是何時被發現的，它們是如何被改進的，以及算法改進的規模與其他創新研究相比結果如何。本文分析了來自 57 部教科書和超過 1137 篇研究論文，以追溯算法何時變得更優。其中一些研究論文直接報告了新算法帶來的好處，而其他研究論文需要使用偽代碼（描述基本細節算法的速記版本）進行重構。

該團隊總共研究了 113 個算法族， 對于每個算法，該團隊都重建了它的歷史，跟蹤每次針對該問題所提出的新算法，并特別強調那些更有效的算法。從 1940 年代到現在，從性能上看，該團隊發現每個算法族平均有 8 個算法，其中有幾個提高了效率。為了共享這個知識數據庫，該團隊還創建了 Algorithm-Wiki.org。

此外，該研究還繪制了這些算法族改進的速度，他們重點關注那些算法中經常被用來分析的特征，這些特征能保證以最快的速度解決問題。

對于大型計算問題，43% 的算法改進等于或大于摩爾定律帶來的益處。在 14% 的問題中，算法對性能的改進大大超過了硬件改進帶來的益處。對于大數據問題，算法改進帶來的益處也非常大，因此算法改進的重要性在近幾十年來不斷增加。

Neil Thompson 與麻省理工學院訪問學生 Yash Sherry 一起撰寫了這篇論文。其中 Thompson 是麻省理工學院計算機科學和人工智能實驗室研究科學家，也是哈佛大學創新科學實驗室的客座教授。他的主要研究領域包括摩爾定律與計算機性能、機器學習與算法等。

Neil Thompson

分析結果

在分析中，研究者著重于具有精確解的精確算法。他們將算法分類為解決不同潛在問題的算法族。例如，合并排序和冒泡排序是比較式排序族中 18 種算法中的兩種。最終，基于一系列標準，研究者共探究了 113 個算法族。

平均而言，每個族有 8 種算法。如果一種算法降低了其算法族的最壞情況漸進時間復雜度，則認為它改進了。基于這一標準，研究中得到了 276 種初始算法和后續改進算法，其中每個算法族中初始算法平均會有 1.44 個改進。

創建新算法

下圖 1 總結了隨時間推移出現的算法發現和改進。其中，1(a) 展示了每個算法族中首個算法出現的時間，通常通過蠻力實現（意味著直接但計算效率低下），1(b) 展示了每十年中算法的份額，其中漸進時間復雜度提升。

例如，20 世紀 70 年代發現了 23 個新的算法族，并對先前發現的所有算法族中的 34% 進行了改進。以后數十年，發現和改進的速度下降了，表明這些算法的進展放緩了。尚不清楚究竟是哪些原因造成的，一種可能的原因是某些算法在理論上已經達到了最優，因此不可能取得進一步發展。

下圖 1 (c) 和 1(d) 分別展示了算法首次被發現時的「時間復雜度類別」分布以及因算法改進使得一類算法轉變為另一類的概率。在算法理論中，時間復雜度類別根據算法本身需要的操作數量（通常表示為輸入大小函數）進行分類。

如 1(c) 所示，在被發現時，31% 的算法族屬于指數復雜度類別（表示為 n!|c^n ）。這意味著隨著輸入大小的增長，算法至少會進行指數級的運算。1(d) 則表明，隨著算法設計者發現更高效的實現方式，算法的復雜度類別會出現重大的轉變。

衡量算法改進

隨著時間推移，算法族的性能會隨著「用更少操作解決相同問題的新算法的出現」而提升。為了衡量進展，研究者著重于提升漸進復雜度的發現，例如從 O(n^2) 到 O(n log n) 或者從 O(n^2.9) 到 O(n^2.8)。

下圖 2 (a) 展示了四個不同算法族（不同顏色表示）隨時間推移出現的進展。對于每個算法族，首個算法的性能都被歸一化為 1。每當發現一種算法具有更高的漸進復雜度時，則由垂直步進（vertical step up）表示。比如，對于 n = 100 萬的問題規模而言，最大子串等算法的改進速度明顯快于硬件或摩爾定律，而自平衡樹創建等其他算法不呈現這種特點。

算法和硬件改進之間的重要對比在于改進的可預測性。雖然摩爾定律使得硬件隨時間推移順利地改進，圖 2 展示了那些經歷了大的但不頻繁的改進的算法。

此外，一種算法的漸進性能關乎于問題輸入大小的函數。隨著輸入的增加，從一個復雜度類別轉變到另一個復雜度類別的改進的規模也在增加。圖 2(b) 展示了「最近鄰搜索」族的這種效果，表明當輸入大小從 10^2 增加至 10^8 時，改進大小也從 15 倍增至約 400 萬倍。

上圖 2 展示了算法改進對四個算法族的影響，下圖 3 將這種分析擴展至了 110 個算法族。具體地，研究者展示了問題規模分別為 1 千、100 百萬和 10 億時平均年度改進率，并將它們與 SPECInt 基準衡量的硬件平均改進率進行比較。

如下圖所示，研究者展示了兩種大的算法族集群，以及一些中間值。

第一個集群代表不到一半的算法族，即使對于大的問題規模而言，它們幾乎沒有出現改進。這個集群可能包含那些獲得很少關注的算法族、在數學上已經達到最優實現并因而無法進一步改進的算法族、那些仍然無法解決某種大小的問題的算法族或者其他。

第二個集群包含 14% 的算法族，它們的年改進率超過 1000%。這些算法受益于指數級加速，例如當初始算法具有指數級時間復雜度時，后續的改進使得問題可以在多項式時間內解決。

研究者的結果量化了算法改進影響計算機科學的兩個重要教訓。

其一，當一個算法族從指數級復雜度過渡到多項式復雜度時，它會以一種硬件改進無法做到的方式轉變該問題的易處理性；

其二，隨著問題規模增加至數十億或萬億個數據點時，就平均年改進率而言，算法改進的重要性比硬件或摩爾定律重要得多。這些發現表明，在擁有大規模數據集的數據分析和機器學習領域，算法改進尤為重要。

算法中的 Step 分析

在整篇文章中，該研究通過查看算法的漸進復雜度來估算算法需要執行的 step 數。

為了估計漸近復雜度近似的保真度，該研究重新分析了算法改進的研究。由于數據庫中只有 11% 的論文報告了算法所需的算法 step 數，因此研究者需要盡可能根據原始論文中的偽代碼描述手動重建 step 數。

使用這種方法，該研究能夠重建 65% 的算法族中第一個和最后一個算法所需的算法 step 數。圖 4 顯示了算法 step 改進和漸近復雜度改進之間的比較。?

圖 4 顯示，在數據可用的情況下，算法 step 數和漸近性能的改進大小幾乎相同。

參考鏈接：

https://news.mit.edu/2021/how-quickly-do-algorithms-improve-0920?

https://ieeexplore.ieee.org/document/9540991

🔍

現在，在「知乎」也能找到我們了

進入知乎首頁搜索「PaperWeekly」

點擊「關注」訂閱我們的專欄吧

·

總結

以上是生活随笔為你收集整理的算法改进有多快？是否比迭代硬件收益更大？这是MIT的结论的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。