🎯 什麼情境該想到我
當你「已經有一個能動的解，但覺得太慢/太笨、想找更漂亮更高效的解法」時。
⚙️ 怎麼用
- 先有正確的暴力解：別一開始就追最優，先確保對。
- 找重複與浪費：哪裡在重算？（→ 記憶化/DP）哪裡在做無用功？（→ 剪枝）
- 換角度重新表述問題：從數學、資料結構、對稱性等不同視角看，常有簡潔解。
- 列出多個解並比較取捨：時間 vs 空間 vs 可讀性，選最適合當前場景的（不一定是漸進最優）。
- 用具體小例子驗證每個新解仍正確。
★ 走一遍：「數一個整數的二進位有幾個 1」的四種解法
這是《編程之美》風格的經典題。以下是四種解法，都用 Go 實測過正確性與速度（Apple M4、Go 1.26.4，1024 個隨機 64 位元整數，2026-09-25）：
// 解 1：逐位檢查 —— 固定跑 64 次（最高位的 1 之後才停）
func shift(x uint64) int {
n := 0
for x != 0 { n += int(x & 1); x >>= 1 }
return n
}
// 解 2：x & (x-1) 會清掉最低位的 1 —— 只跑「1 的個數」次
func kernighan(x uint64) int {
n := 0
for x != 0 { x &= x - 1; n++ }
return n
}
// 解 3：查表 —— 預先算好 0~255 的答案，一次處理 8 個位元
var tbl [256]uint8 // init 時用解 1 填好
func table(x uint64) int {
n := 0
for i := 0; i < 8; i++ { n += int(tbl[x&0xff]); x >>= 8 }
return n
}
// 解 4：標準函式庫（編譯器在支援的 CPU 上會用硬體指令）
bits.OnesCount64(x)| 解法 | 每個數平均耗時 | 看到的「浪費」 | 換來的代價 |
|---|---|---|---|
| 逐位檢查 | ~19.6 ns | 對每個 0 位元也做一次迴圈 | — |
x & (x-1) | ~18.7 ns | 只迭代 1 的個數 | 需要知道這個位元技巧 |
| 查表 | ~2.8 ns | 把重複計算搬到預先計算 | 256 bytes 記憶體、init 時間 |
bits.OnesCount64 | ~0.93 ns | 交給硬體 | 無（這就是正解） |
兩個反直覺的觀察：
- 解 2 在隨機輸入上幾乎沒比解 1 快：隨機 64 位元整數平均有 32 個 1，迴圈次數只少一半，而且每一輪的依賴鏈更長。它的優勢只在「1 很稀疏」的輸入上才明顯——最佳化的效果取決於資料分布。
- 最快的解法是呼叫標準函式庫。先查「這個問題標準函式庫有沒有解」，是最被低估的最佳化步驟。
★ 找更好解法的五個方向
| 方向 | 問自己 | 例子 |
|---|---|---|
| 消除重複計算 | 有沒有子問題被算了好幾次？ | 遞迴 Fibonacci → 記憶化 → 迭代，O(2ⁿ) → O(n) |
| 預先計算 | 有沒有東西可以提前算好、查詢時直接用？ | 查表法；前綴和讓區間和從 O(n) → O(1) |
| 換資料結構 | 最常做的操作在目前結構上是不是很慢？ | 在 slice 裡找元素 O(n) → 用 map O(1)（見 工具-資料結構的選擇） |
| 利用題目的特殊性質 | 輸入有沒有排序、範圍有限、有結構？ | 已排序 → 二分搜尋；值域小 → 計數排序 |
| 換個角度表述 | 能不能反過來算、轉換成已知問題？ | 「找缺少的數字」→ 用總和減去實際總和（或 XOR） |
★ 什麼時候停
- 量過了，真的是瓶頸嗎？ 在一個每秒呼叫 10 次的函式上把 20 ns 降到 1 ns，對系統沒有任何可見的影響。
- 新解法的正確性證明得了嗎？ 上面四個解法都用同一組 1024 個輸入比對過結果，才進行計時。先有對照測試，才能大膽換解法。
- 可讀性的代價值得嗎？ 查表法比逐位檢查難讀一點；如果它不在熱路徑上，用最清楚的寫法（見 工具-簡單清楚至上）。
🧪 我實際套用的紀錄
- 2026-07-15：（待填）
⚠️ 注意
-
最優解不總是最好選擇；若可讀性/維護性代價太高，簡單夠快的解更務實（見 工具-簡單清楚至上）。
-
benchmark 數字只在同一台機器、同一版本上可比：上表的絕對數字換了 CPU 就會變，但相對排序與「差一個數量級」的結論通常穩定。
-
Go 的 benchmark 要防止被編譯器最佳化掉：結果要寫到一個套件層級變數（例如
sink += f(x)），否則沒有被使用的計算可能直接被刪掉。Go 1.24+ 的for b.Loop() { … }會讓語法上直接寫在迴圈大括號內的函式呼叫參數與結果保持存活，不會被整段最佳化掉（依 Go 1.26.4testing.B.Loop文件，2026-09-25）；寫在迴圈外的輔助函式裡的計算不受此保護。
🔗 相關工具
- 工具-演算法設計策略 —— 找第二解時的搜尋方向：先辨認題目屬於哪種策略，比亂試有效率
- 工具-用類比解決新問題 —— 另一條找解路徑：想不出新解法時，從解過的相似問題借結構
- 工具-時間複雜度分析 —— 判斷「新解真的比較好嗎」的量尺，避免只是換個寫法卻沒變快