Greg Colvin

Man’s got to know his limitations. —Dirty Harry

資源是有限的#

你只有這麼多時間和金錢來完成工作，包括維持你的知識、技能和工具所需的時間與金錢。你只能這麼努力、這麼快、這麼聰明，且只能持續這麼久。你的工具只有這麼強大，你的目標機器也只有這麼強大。所以你必須尊重資源的極限。

認識你的極限#

如何尊重這些極限？了解你自己、你的團隊、你的預算和你的東西。特別是身為軟體工程師，要了解你的資料結構和演算法的空間與時間複雜度，以及系統的架構和效能特性。你的工作是打造軟體和系統的最佳組合。

複雜度分析#

空間和時間複雜度以函式 O(f(n)) 表示，其中 n 等於輸入大小，代表 n 趨近無窮時所需的漸進空間或時間。重要的複雜度等級包括：

• O(ln(n))、O(n)、O(n ln(n))：近常數到近線性，通常是可接受的
• O(n²)、O(eⁿ)：近無限，在大規模資料下會變得不可承受

真實機器的限制#

複雜度分析基於抽象機器，但軟體運行在真實機器上。現代計算機系統是物理和虛擬機器的層級結構，包括語言執行期、作業系統、CPU、快取、RAM、硬碟和網路。

容量和速度差距高達數個數量級。快取和預讀（lookahead）被大量使用來隱藏這些差異，但只在存取模式可預測時有效。當 cache miss 頻繁發生，系統就會顛簸（thrashing）。

演算法與快取效率#

演算法和資料結構在使用快取的效率上有很大差異。例如搜尋 64 位元整數陣列的三種方法：

• Linear search（線性搜尋）：對小陣列具競爭力，但大陣列時呈指數級劣化
• Binary search（二元搜尋）：需要 O(log(n)) 次比較
• van Emde Boas tree 搜尋：O(log(n)) 且對快取友善（cache-oblivious）

You pays your money and you takes your choice. —Punch（你花你的錢，做你的選擇。）了解你的資源極限，選擇最適合實際情況的方案。