avaScript 算法基礎第 1 部分：什么是算法？ 解決特定問題時必須遵循的一組規則。

讓我們從關于算法的非常基本的問題開始。

什么是算法？

解決特定問題時必須遵循的一組規則。

這是您在 Google 上搜索“算法”時會看到的基本定義。讓我們理解它，這里的“規則集”是指解決特定問題必須遵循的一系列指令。這意味著，如果我們對一個問題遵循相同的規則集和相同的輸入，那么它總是會導致相同的解決方案。這就是算法背后的核心思想。

作為程序員，我們編寫的任何程序都被視為算法，因為它遵循上述相同的基本規則。例如，如果我們創建一個函數來將一個數字與另一個數字相加，那么我們在那里也有一個算法。而且，作為程序員，我們的目標是找到最有效的問題解決方案。這意味著我們將始終尋求解決特定問題的最佳可用解決方案，因為將有多種方法來解決它。現在我們遇到的問題是，我們如何找到最佳的可用解決方案？

如何找到最好的算法？

當我們談論找到給定問題的最佳解決方案時，我們可以考慮以下幾點：

• 它是消耗最少內存的算法嗎？
• 是代碼量最少的算法嗎？
• 是花費最少時間的算法嗎？

最好的解決方案很可能取決于我們工作的條件。但通常它會是執行時間最少的那個。因此，我們應該尋找執行時間最少的算法。但是，我們如何衡量算法的時間呢？

測量算法的時間復雜度（使用時間差）

讓我們用一個例子來看看我們如何測量算法的時間復雜度。

示例問題

編寫一個函數，將數字作為輸入，然后返回所有數字的總和。

功能：此功能可以在 JavaScript 中實現如下。

const n=[1, 2, 3, 4, 5];    // Inputfunction sum(n) {
  let total=0;
  for (let index=0; index < n.length; index++) {
    total +=n[index];
  }
  return total;
}console.log(sum(n));         // 15 

上面的函數接受一個數字數組作為參數，用 0 初始化總數，然后在 for 循環中我們遍歷數組中的所有數字，添加到總數中，最后返回總數。

例如，如果我們使用數組作為 [1, 2, 3, 4, 5] 調用函數，那么我們得到的結果為 15（即 1 + 2 + 3 + 4 + 5）。 所以這是我們解決上述問題的第一個算法。

現在，讓我們看看如何衡量它所花費的時間。

為此，一種簡單的方法是通過計算函數的開始時間和結束時間之間的差異來測量時間。 這可以在 JavaScript 中如下所示完成。

let startTime=0;
let endTime=0;
let timeToExecute=0;startTime=performance.now();
sum([1, 2, 3, 4, 5]);
endTime=performance.now();
timeToExecute=endTime - startTime;

timeToExecute 將為我們提供函數的執行時間。 讓我們嘗試找出具有幾個不同參數的函數所花費的時間。 我們將在兩個不同的設備上執行此操作，一個在較慢的設備上，另一個在較快的設備上。

在較慢的設備上執行上述功能：

sum([1,2,3,4,5,6,7,8,9,10]);
// 0.19999980926513672 -> Timesum([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);
// 0.2999999523162842  -> Timesum([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40]);    
// 0.40000009536743164  -> Time

在更快的設備上執行上述功能：

sum([1,2,3,4,5,6,7,8,9,10]);  
// 0  -> Timesum([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);
// 0  -> Timesum([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40]);
// 0  -> Time

現在，如果我們在較慢的設備和較快的設備上查看結果輸出，您會發現時間并不總是相同的。在慢速設備上，它會隨著陣列大小的增加而逐漸增加。但是，在速度更快的設備上，它是恒定的。

同樣，假設我們對同一問題有另一種解決方案，我們認為它比上述實現更快，但結果相同，即在更快的設備上為 0，那么我們很難在兩者中找出最佳解決方案.因此，根據這些具體數字來測量時間并不是正確的方法。因為它有很多與我們的算法無關的影響因素。例如，我們正在運行的設備硬件很重要。

正如我們在上面看到的，在舊設備上，我們看到不同的數字。可能還有其他影響因素，比如后臺運行的進程數、可用內存量較少等。那么，我們應該如何衡量函數時間呢？

測量算法的時間復雜度（使用模式）

答案在于我們在不同輸入下看到的模式，我們將在此處參考較慢設備的結果，其中對于數組中傳遞的更多數字往往需要更長的時間。

一般來說，我們可以說的是，數組中的數字越多，所需的時間就越長。而且，模式中似乎很常見的一件事是時間隨著數組大小的增加而增加。事實上，這就是我們應該如何看待它。

我們不應該太在意具體數字，因為這些取決于上面看到的環境中的許多因素。但我們應該始終尋找這種和類似的一般模式。所以對于這個函數，如果你想畫一個圖形，它大概是這樣的。

這是一個線性圖，因為我們在上述函數中看到的模式是線性的。我們看到函數所花費的時間隨著數組大小的增加而增加。而且，時間的增加與數組大小的增加成正比。所以我們可以說增長是線性的，因此我們在這里有一個線性增長函數。

我們增加輸入的因子，在我們的例子中（n）（即數組中的數字）是時間函數增加的因子。

這就是我們在談論算法時判斷性能的方式。我們查看時間的函數，即我們看到的模式，而不是實際時間，以便能夠通過算法對輸入的反應時間來評估算法的性能。而且，我們也稱其為時間復雜度。在這種情況下，我們可以說求和函數和算法具有線性時間復雜度。

上述問題的另一種解決方案（線性時間與恒定時間）

在 JavaScript 中，并非所有算法都需要線性時間。有時我們的算法需要固定的時間。在這種情況下，輸入的數量不會影響該算法所花費的時間。我們可以通過修改前面的示例來看到這一點，如下所示，以接受數字作為不同的參數而不是數組。

function sum(n1, n2, n3, n4, n5) {
  return n1 + n2 + n3 +n4 +n5;
}sum(1, 2, 3, 4, 5)   // 15

在這種情況下，該函數接受五個參數并返回所有參數的總和。 這也是解決上述問題的另一種方法，我同意這不是最佳解決方案，因為參數的數量是固定的，如果我們需要更多的數字來傳遞參數，那么我們將不得不為 它。

但是，它仍然解決了問題，即計算所有通過的數字的總和。 但是，當我們比較這兩個函數時，需要注意一個重要的區別。 修改后的函數沒有循環，而是只有一個數學公式。

現在，如果我們嘗試通過使用與循環應用到前一個函數相同的參數來執行上述函數來測量時間，你會看到這里的結果是恒定的。

sum(1,2,3,4,5,6,7,8,9,10);
// 0  -> Timesum(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30);
// 0  -> Timesum(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40);
// 0  -> Time

而且，無論我們傳遞多少參數，它都保持不變。 我們在這里也沒有任何模式，因為我們以前有不同的數組大小。 我們可以將其視為恒定時間的示例。 具有恒定時間復雜度的圖看起來像這樣。

因此，通過比較上述兩種算法的時間復雜度，即循環的函數（指較慢設備的結果）和數學公式的函數，我們可以說一個具有線性時間復雜度，另一個具有恒定時間復雜。

模式方法可靠嗎？

然而，這里有一個問題，如果我們在一個速度非常快的設備上執行這兩個函數，結果是恒定的時間值怎么辦？我們在這里做什么？因為我們剛剛遵循的模式方法無法應用，因為那里沒有模式，因為結果是恒定的。

在這種情況下，我們可能會做出錯誤的判斷，并將兩個函數的時間復雜度視為常數，而我們剛剛在較慢的設備示例中看到的情況并非如此。因此，即使這種通過基于時間識別模式來識別函數時間復雜度的技術也是不可靠的，因為它受到很多因素的影響。但是，我們確實有一種可靠的方法來評估算法，我們將在以后的帖子中對其進行研究。

感謝您的閱讀。

關注七爪網，獲取更多APP/小程序/網站源碼資源！

雯 發自 凹非寺
量子位 報道 | 公眾號 QbitAI

5月中旬剛剛結束的Pycon US 2021上，Python之父Guido van Rossum提出要在未來四年內將CPython速度提升5倍。

而這一“Shannon計劃”的參與者除了Guido本人之外，還有任職微軟的CPython核心開發人員Eric Snow，以及Semmle的研究工程師Mark Shannon。

但在此之前，Guido可并不認為提升CPython的速度有多關鍵，因為“有其他方法可以獲得更好的性能”，比如JIT編譯的PyPy，或使用C語言編寫擴展。

為什么要加速？

Python真的慢嗎？

不見得，開發效率和執行速度本就難以兼得。

而且發展到今天，Python已經是一個膠水語言的定位，主要用來快速構建系統的邏輯控制流，再把對性能要求高的部分丟給C/C++來實現。

不過如果只看標準版的語言實現本身的話……它的性能確實不怎么樣。

動態語言的特性決定了Python會在C語言代碼運行（runtime）上花費大量的時間，且難以使用JIT（Just-In-Time）進行優化。

在接受英國技術新聞網站The Register的采訪時，對于“為什么開始關注CPython性能？”的問題，Shannon表示：

過去幾年里，Python在機器學習領域的使用率大大提升，可用資源也越來越多。這意味著我們可以不用擔心破壞其可靠性，而是專注在性能上。

并且，Shannon之前參與的HotPy項目中所開發的解釋器，比目前CPython解釋器的純Python代碼快三倍。這證明了對CPython優化的可行性。

而在去年10月份的時候，耐不住退休寂寞的Guido又加入了微軟：

再加上疫情的家里蹲buff，擁有了更多時間的大佬們一拍即合，決定Make Python Great Again。

加速之前的挑戰

Shannon坦言，向下兼容是加速Python的最大挑戰。

其實不僅是對Python，90年代末libc的那次不兼容更新，直接導致所有應用程序都要重編……

而現在已經涼涼的Pyston，官方文章里提到的Dropbox放棄Pyston項目的幾大因素中，第一個也是：

這就是所有既試圖兼容CPython，又想大幅提升性能的Python都會遇到的嚴峻問題。

因為Python的執行類似于HTML渲染：更多是對運行時應如何執行C庫的描述，而非單步執行命令。

所以，Python性能提升的源頭來自于這些C擴展模塊。而CPython又有著超過400k的loc，這意味著要從底層去做優化是一項非常龐大的工程。

特別是對于過于動態的Python語言來說，語言的語義對優化的影響就更大了。

而現在加速的過程中，像是CPython的工具、調試器、配置文件，NumPy包，以及Cython這樣的編譯器，又會有多少涉及到CPython內部和底層的行為？

因此Shannon表示：

要改變是困難的……與CPython用戶間的隱形協議并沒有很好地定義什么能改，什么不能改。

可能是五年前從Python2.x遷移到3的痛苦經歷實在是有些刻骨銘心，Guido專門發推表示這次的遷移會更加平和。

而他也在Python峰會中承諾：不破壞stable ABI兼容性；不破壞limited API兼容性；不破壞或減緩extreme cases。

“總之，代碼的可維護性才是第一要務。”

Python的5倍速之路

按照已在GitHub上發布的faster-cpython，Shannon計劃具體分為四個階段：

Python 3.10

預計在今年10月發布，主要添加一個自適應、專業化的解釋器（interpreter）。

解釋器將不在運行時生成代碼，而是利用程序中的類型穩定性，在執行過程中適應類型和數值。

Python 3.11

Guido提出要在3.11版本實現至少2倍的提速，為此，他已經和幾位Python開發人員提出了一份增強功能的提案PEP 659。

這一提案中表示要增加適應性的字節碼解釋器，并且實施更有效的異常處理。

除此之外，還提出了優化幀堆棧、改變函數調用的方式、增加優化以加快啟動時間，以及修改 .pyc 字節碼緩存文件格式等工作。

Python 3.12

這一階段使用針對小區域的JIT解釋器，在運行代碼時簡單、快速地對小區域的專門代碼進行編譯。

Python 3.13

同樣在代碼運行時對擴展區域進行編譯，增強編譯器，以完成5倍的超級加速。

Guido表示此次圍繞性能展開的 Python 變更，將主要服務于運行CPU密集型純Python代碼的開發者，以及內置Python網站的用戶。

而在C語言代碼（如 NumPy和TensorFlow）、I/O 綁定代碼、多線程代碼以及算法代碼上，提升效果將會比較有限。

微軟回饋Python

其實，微軟長期以來一直以多種方式為Python項目提供助力，包括在Azure云AI服務教程里發布免費的Python課程，以及通過VS Code Python擴展在Win10及以上版本支持Python。

自 2006 年起，微軟還成為了Python軟件基金會（PSF）的贊助商，并在今年出資15 萬美元進行資助。

目前已有五位Python開發者社區的核心人員在微軟任職，包括去年年底加入的Python之父，和這次Shannon計劃里的三人之一Eric Snow。

Guido也在這次峰會里特地cue了一下微軟，提出微軟資助了一支小型Python團隊“負責語言解釋層面的性能改進工作”，以使他能攜手微軟同事持續對Python進行開發。

當然，對于3.11版本的短期目標，Guido還是在ppt中給自己兜了個底。

而對于那個四年五倍速的最終目標，Guido則表示“我們必須保持旺盛的創造力。”

參考鏈接：
[1]https://www.theregister.com/2021/05/19/faster_python_mark_shannon_author/
[2]https://pyfound.blogspot.com/2021/05/the-2021-python-language-summit-pep-654.html
[3]https://www.python.org/dev/peps/pep-0654/

Python version 3.11.0 alpha 0：
https://github.com/faster-cpython/ideas
“A faster CPython”計劃簡介：
https://github.com/markshannon/faster-cpython

— 完 —

量子位 QbitAI · 頭條號簽約

關注我們，第一時間獲知前沿科技動態