C++ 自製的 gcd 比標準函式庫提供的跑得還要快？

今天在用 C++ 重複練習 2197. Replace Non-Coprime Numbers in Array 一遍，試著寫出跑得更快的版本，發現自己寫出來的 gcd 在 LeetCode 平台上反而跑得比較快，目前還不曉得背後到底是怎麼一回事，先記錄一下，目前想到的做法是盡量避免呼叫 gcd 以及盡量使用已使用的記憶體空間來加速，最好的時候可以跑到 Runtime 2ms Beats 98.62% 的成績。

class Solution {
    int gcd(int a, int b) {
        if (b > a)
            swap(a, b);
        while (b != 0) {
            a %= b;
            swap(a, b);
        }
        return a;
    }

public:
    vector<int> replaceNonCoprimes(vector<int>& nums) {
        int idx = 0;
        for (int i = 1; i < nums.size(); ++i) {
            int num = gcd(nums[idx], nums[i]);
            if (num == 1)
                nums[++idx] = nums[i];
            else
                nums[idx] = nums[idx] / num * nums[i];
            for (int j = idx; j > 0; --j) {
                int num = gcd(nums[j], nums[j - 1]);
                if (num == 1)
                    break;
                nums[j - 1] *= nums[j] / num;
                --idx;
            }
        }
        nums.resize(idx + 1);
        return nums;
    }
};

Rust 沒官方標準支援 gcd 跟 lcm 的 traits 蠻令人意外的

今天在練習 2197. Replace Non-Coprime Numbers in Array 時，需要使用到 GCD 跟 LCM，在 C++/Python 都有官方支援，Rust 跟 Go 都沒有支援，有點意外。

impl Solution {
    pub fn replace_non_coprimes(nums: Vec<i32>) -> Vec<i32> {
        let mut arr = Vec::with_capacity(nums.len());
        let mut curr = nums[0];
        let gcd = |mut a: i32, mut b: i32| -> i32 {
            if a < b {
                (a, b) = (b, a);
            }
            while b != 0 {
                (a, b) = (b, a % b);
            }
            a
        };
        let lcm = |a: i32, b: i32| -> i32 {
            a / gcd(a, b) * b
        };
        for &num in &nums[1..] {
            if gcd(num, curr) > 1 {
                curr = lcm(num, curr);
                while let Some(&last) = arr.last() && gcd(curr, last) > 1 {
                    curr = lcm(last, curr);
                    arr.pop();
                }
            } else {
                arr.push(curr);
                curr = num;
            }
        }
        arr.push(curr);
        arr
    }
}

這裡還剛好可以使用到 Rust 1.88 版本才開始有支援的 Let chains，Let chains 讓程式碼的表示更直白，真是太棒了。

if let Channel::Stable(v) = release_info()
    && let Semver { major, minor, .. } = v
    && major == 1
    && minor == 88
{
    println!("`let_chains` was stabilized in this version");
}

基於四底對數的整數級數求和

***此篇文章由 Gemini AI 產生*** ### **問題定義** 我們的目標是計算一個特定總和 `S`，這個總和是由一個函數 `f(i) = ⌊log₄(i)⌋ + 1` 對所有從 1 到 `4^p - 1` 的整數 `i` 的值累加而成。其數學表達式為： $$S_p = \sum_{i=1}^{4^p-1} \left( \lfloor \log_4(i) \rfloor + 1 \right)$$ 這裡的 `p` 是一個正整數。 --- ### **公式推導** 直接計算這個總和很困難，關鍵在於觀察函數 `f(i)` 的特性。`f(i)` 的值在一系列連續的整數區間內是恆定的，這些區間由 4 的次方所界定。 #### **步驟一：級數的轉換** 1. **分析函數值**： * 對於任何落在區間 $[4^k, 4^{k+1} - 1]$ 內的整數 `i`，`log₄(i)` 的值會介於 `k` 與 `k+1` 之間 (即 `k ≤ log₄(i) < k+1`)。 * 因此，`⌊log₄(i)⌋` 的值恆為 `k`。 * 所以，對於這個區間內的所有 `i`，函數 `f(i)` 的值恆為 `k+1`。 2. **計算區間內的整數數量**： * 在區間 $[4^k, 4^{k+1} - 1]$ 中，整數的數量為： $$(4^{k+1} - 1) - 4^k + 1 = 4^{k+1} - 4^k = 4^k(4-1) = 3 \cdot 4^k$$ 3. **重寫總和表達式**： * 我們的總和 $S_p$ 是加總到 $4^p - 1$，這恰好涵蓋了從 `k=0` 到 `k=p-1` 的所有完整區間。 * 因此，我們可以將原本對 `i` 的求和，轉化為對 `k` 的分組求和： $$S_p = \sum_{k=0}^{p-1} (\text{區間內函數的值}) \times (\text{區間內的整數數量})$$ $$S_p = \sum_{k=0}^{p-1} (k+1) \cdot (3 \cdot 4^k)$$ #### **步驟二：求解等比等差數列** 我們可以將常數 3 提出，得到一個**等比等差數列**的和： $$S_p = 3 \cdot \sum_{k=0}^{p-1} (k+1) \cdot 4^k$$ 令核心部分為 `A`： $$A = \sum_{k=0}^{p-1} (k+1) \cdot 4^k = 1 \cdot 4^0 + 2 \cdot 4^1 + 3 \cdot 4^2 + \dots + p \cdot 4^{p-1}$$ 我們使用**錯位相減法**來求解 `A`。首先將 `A` 乘以級數的公比 4： $$4A = 1 \cdot 4^1 + 2 \cdot 4^2 + \dots + (p-1) \cdot 4^{p-1} + p \cdot 4^p$$ 接著，將 `A` 減去 `4A`： $$-3A = (1 \cdot 4^0 + 2 \cdot 4^1 + \dots + p \cdot 4^{p-1}) - (1 \cdot 4^1 + 2 \cdot 4^2 + \dots + p \cdot 4^p)$$ 合併同類項後，算式變為： $$-3A = 1 \cdot 4^0 + (2-1) \cdot 4^1 + (3-2) \cdot 4^2 + \dots + (p - (p-1)) \cdot 4^{p-1} - p \cdot 4^p$$ 這可以簡化為一個等比級數與一個單項： $$-3A = (4^0 + 4^1 + 4^2 + \dots + 4^{p-1}) - p \cdot 4^p$$ 括號中的部分是一個首項為 1，公比為 4，共有 `p` 項的等比數列。其和為 $\frac{4^p - 1}{4 - 1} = \frac{4^p - 1}{3}$。代入上式： $$-3A = \frac{4^p - 1}{3} - p \cdot 4^p$$ 為了求解 `A`，我們繼續整理。兩邊同乘以 -1： $$3A = p \cdot 4^p - \frac{4^p - 1}{3}$$ 通分整理後： $$3A = \frac{3p \cdot 4^p - (4^p - 1)}{3}$$ 最終得到： $$3A = \frac{(3p - 1) \cdot 4^p + 1}{3}$$ --- ### **最終公式** 我們最初的目標是 $S_p = 3 \cdot A$。將 `A` 的結果代入，即可得到該總和的封閉形式解（closed-form solution）： $$S_p = \frac{(3p - 1) \cdot 4^p + 1}{3}$$ 這個公式允許我們直接代入 `p` 來獲得最終結果，而無需進行迭代求和。 --- ### **範例驗證 (p=2)** 現在我們設定 `p = 2` 來驗證公式的準確性。我們要計算從 `i = 1` 到 `4² - 1 = 15` 的總和： $$S_2 = \sum_{i=1}^{15} \left( \lfloor \log_4(i) \rfloor + 1 \right)$$ #### **方法一：直接套用公式** 將 `p = 2` 代入我們推導出的公式，逐步計算： $$S_2 = \frac{(3 \cdot 2 - 1) \cdot 4^2 + 1}{3}$$ $$S_2 = \frac{(6 - 1) \cdot 16 + 1}{3}$$ $$S_2 = \frac{5 \cdot 16 + 1}{3}$$ $$S_2 = \frac{80 + 1}{3}$$ $$S_2 = \frac{81}{3} = 27$$ 公式計算出的結果是 **27**。 #### **方法二：分組逐項計算** 我們也可以將 1 到 15 的數字分組來計算實際總和： 1. **第一組 (k=0):** 當 `i` 在區間 `[1, 3]` * 包含的數字：1, 2, 3 (共 3 個) * 對於這些數字，`⌊log₄(i)⌋ + 1` 的值皆為 `0 + 1 = 1`。 * 此組的總和為： 3 個數字 × 1 = 3 2. **第二組 (k=1):** 當 `i` 在區間 `[4, 15]` * 包含的數字：4, 5, ..., 15 (共 `15 - 4 + 1 = 12` 個) * 對於這些數字，`⌊log₄(i)⌋ + 1` 的值皆為 `1 + 1 = 2`。 * 此組的總和為： 12 個數字 × 2 = 24 **總和** = 第一組總和 + 第二組總和 = `3 + 24 = 27`。 兩種方法得到的結果 **27** 完全相同。

想算數字裡有幾個 1？C++, Python3, Go, Rust 大亂鬥！

***此篇文章由 Gemini AI 產生*** 哈囉，各位寫 code 的夥伴們，大家好！ 今天我們來聊一個面試或刷題時偶爾會碰到，但其實也蠻有趣的小問題：「怎麼計算一個數字在二進位下有幾個 1？」 聽起來好像很學術，但別擔心，其實觀念很簡單。比方說，數字 5，寫成二進位是 `101`，那它就有兩個 1。數字 7，二進位是 `111`，就有三個 1。這在某些演算法或需要操作底層位元（bit）的場景，其實還蠻實用的。 今天我們就來看看用四種現在很夯的語言：C++, Python3, Go, 和 Rust，要怎麼解決這個問題。順便比較一下它們的寫法和「個性」有什麼不一樣。 #### C++：硬底子真功夫，效能我最強 C++ 就是那個班上最認真、對所有細節都一清二楚的學霸。要解決這個問題，C++ 提供了一個超級方便的內建函式（built-in function），不過在比較舊的 C++ 版本可能需要自己手刻。 在比較新的 C++ 標準 (C++20) 中，你可以直接用 `` 這個函式庫： ```cpp #include #include int main() { int num = 77; // 77 的二進位是 1001101 // std::popcount 會直接幫你數好有幾個 1 int count = std::popcount(static_cast<unsigned int>(num)); std::cout << "數字 " << num << " 裡有 " << count << " 個 1！" << std::endl; // 輸出: 數字 77 裡有 4 個 1！ return 0; } ``` **重點分析：** * **`std::popcount`**: 這名字超直白，「pop」在這裡指的是 "population"（總數），所以 `popcount` 就是「計算總數」。這是編譯器等級的優化，速度快到飛起來。 * **`static_cast<unsigned int>`**: 這是在做「型別轉換」。因為 `popcount` 通常是針對無號整數 (unsigned) 操作的，所以我們先把 `num` 轉成無號整數，避免一些奇怪的問題。 C++ 的寫法就是這麼樸實無華且枯燥，但效能絕對是頂尖的！ #### Python3：人生苦短，我用 Python Python 就是那個朋友群裡最會聊天的萬人迷，語法親切又好懂。解決這個問題，方法多到你可以自己選。 最直覺的方法，就是直接把它變成二進位字串，然後數裡面有幾個 '1'。 ```python num = 77 # 77 的二進位是 1001101 # bin(num) 會回傳 '0b1001101' # 我們用 .count('1') 來數 '1' 的數量 count = bin(num).count('1') print(f"數字 {num} 裡有 {count} 個 1！") # 輸出: 數字 77 裡有 4 個 1！ ``` 如果你是 Python 3.10 以上的版本，還可以用一個更潮的寫法： ```python num = 77 count = num.bit_count() # 直接呼叫！ print(f"數字 {num} 裡有 {count} 個 1！") # 輸出: 數字 77 裡有 4 個 1！ ``` **重點分析：** * **`bin()`**: Python 的內建函式，可以馬上把數字轉成 `0b` 開頭的二進位字串，超方便。 * **`.count('1')`**: 字串的 method，用來計算某個字元出現的次數。 * **`.bit_count()`**: 在新版 Python 中，整數自己就有這個 method，寫起來更乾淨，而且底層的效能也很好。 Python 的寫法就是這麼優雅，幾行就搞定，可讀性超高。 #### Go：簡單、可靠，Google 親兒子 Go 語言給人的感覺，就像是個務實的工程師，不喜歡花俏的東西，但該有的都有，而且跑起來穩定又快速。 Go 在標準函式庫 `math/bits` 裡面，也直接提供了需要的功能。 ```go package main import ( "fmt" "math/bits" ) func main() { var num uint = 77 // 77 的二進位是 1001101 // Go 推薦使用無號整數 (uint) 來做位元運算 count := bits.OnesCount(num) fmt.Printf("數字 %d 裡有 %d 個 1！\n", num, count) // 輸出: 數字 77 裡有 4 個 1！ } ``` **重點分析：** * **`import "math/bits"`**: Go 把跟位元操作相關的功能都整理在這個 package 裡，分工很清楚。 * **`bits.OnesCount()`**: 函式名稱也是簡單明瞭，就是「計算 1 的數量」。 * **`var num uint = 77`**: Go 是一個強型別語言，它會建議你，在做位元運算時，最好一開始就宣告成無號整數 (`uint`)，這樣語意更明確。 Go 的風格就是這樣，清楚、直接，而且效能也很棒。 #### Rust：安全、並行，程式界的超級英雄 Rust 是這幾年超級紅的語言，主打的就是「安全」跟「極致效能」。它給人的感覺有點像 C++ 的進化版，嚴格但能讓你寫出非常可靠的程式碼。 Rust 在整數型別上，也直接內建了計算 1 數量的方法。 ```rust fn main() { let num = 77_i32; // 77 的二進位是 1001101 // _i32 是告訴編譯器，這是一個 32 位元的整數 // 直接在數字後面呼叫 .count_ones() let count = num.count_ones(); println!("數字 {} 裡有 {} 個 1！", num, count); // 輸出: 數字 77 裡有 4 個 1！ } ``` **重點分析：** * **`_i32`**: 這是 Rust 的語法糖，用來標明數字的型別，`i32` 代表 32 位元有號整數。Rust 對型別非常嚴格，所以寫清楚是好習慣。 * **`.count_ones()`**: Rust 把這個功能直接做成整數型別的一個 method，只要是數字，後面加上 `.count_ones()` 就能用，非常直覺。 Rust 的寫法兼具了 C++ 的效能和 Python 的簡潔，而且還有編譯器這個超級保母在後面幫你檢查，讓你寫 code 超有安全感。 ----- ### 總結一下 | 語言 | 主要寫法 | 風格特色 | | --- | --- | --- | | **C++** | `std::popcount(num)` | 效能至上，語法較嚴謹 | | **Python3** | `bin(num).count('1')` 或 `num.bit_count()` | 語法甜美，可讀性高，快速開發 | | **Go** | `bits.OnesCount(num)` | 務實可靠，標準庫功能齊全 | | **Rust** | `num.count_ones()` | 安全第一，語法現代且效能強悍 | 今天這個小問題，其實四種語言都有非常簡單、高效的解法。從這些小地方，我們也可以稍微窺探出不同程式語言在設計哲學上的差異。 沒有最好的語言，只有最適合的工具。希望這篇簡單的比較，能幫助大家對這幾種語言有更具體的認識。下次不管你用哪種語言，碰到要數 1 的時候，就知道該怎麼做了吧！ Happy coding！

C++/Python3/Go/Rust 關於 list/array/vector 的 sort 在設計上的不同差異

***此篇文章由 Gemini AI 產生*** 在軟體開發中，排序幾乎可以說是最常見的需求之一。然而，不同的程式語言在排序功能的設計上卻有著一些有趣的差異。這篇文章將帶您一探究竟，比較 C++、Python、Go 和 Rust 中 `list`、`array` 或 `vector` 等資料結構的排序（sort）功能，並透過程式碼範例，讓您更深入了解它們在設計上的不同之處。 ### C++：回傳布林值的比較函式 C++ 的 `std::ranges::sort`（以及舊版的 `std::sort`）在自訂排序行為時，需要傳入一個比較函式（Comparison Function），而這個函式必須回傳布林值（`bool`）。 這個比較函式通常接收兩個參數，並在這兩個參數之間進行比較。如果第一個參數應該排在第二個參數之前，則回傳 `true`，否則回傳 `false`。 ```cpp #include #include #include #include struct Person { std::string name; int age; }; int main() { std::vector<Person> people = { {"Alice", 30}, {"Bob", 25}, {"Charlie", 35} }; // 使用 lambda 運算式定義比較函式，按年齡升序排序 std::ranges::sort(people, [](const Person& a, const Person& b) { return a.age < b.age; }); for (const auto& person : people) { std::cout << person.name << " (" << person.age << ")" << std::endl; } return 0; } ``` **輸出結果：** ``` Bob (25) Alice (30) Charlie (35) ``` ### Python：提供 Key Function 提取比較值 Python 的 `list.sort()` 方法則提供了另一種更為簡潔的自訂排序方式。您可以傳入一個名為 `key` 的參數，這個 `key` 參數會接收一個函式，用來從每個元素中提取一個用於比較的「鍵」（key）。 這種設計的好處是，您不需要撰寫一個完整的比較函式，只需要提供一個簡單的函式來告訴 `sort()` 方法要用哪個值來進行排序即可。 ```python class Person: def __init__(self, name, age): self.name = name self.age = age people = [ Person("Alice", 30), Person("Bob", 25), Person("Charlie", 35) ] # 使用 lambda 函式作為 key，按年齡升序排序 people.sort(key=lambda person: person.age) for person in people: print(f"{person.name} ({person.age})") ``` **輸出結果：** ``` Bob (25) Alice (30) Charlie (35) ``` ### Go：回傳 -1, 0, 1 的比較函式 Go 語言的 `slices.SortFunc` 則採用了另一種常見的比較函式設計。您需要傳入一個比較函式，這個函式會回傳一個整數，用來表示兩個元素的相對順序： * **-1**：如果第一個元素應該排在第二個元素之前。 * **0**：如果兩個元素相等。 * **1**：如果第一個元素應該排在第二個元素之後。 ```go package main import ( "fmt" "slices" ) type Person struct { Name string Age int } func main() { people := []Person{ {"Alice", 30}, {"Bob", 25}, {"Charlie", 35}, } // 按年齡升序排序 slices.SortFunc(people, func(a, b Person) int { if a.Age < b.Age { return -1 } if a.Age > b.Age { return 1 } return 0 }) fmt.Println(people) } ``` **輸出結果：** ``` [{Bob 25} {Alice 30} {Charlie 35}] ``` ### Rust：兩種方式，任君挑選 Rust 在排序功能的設計上，可以說是集各家之大成，提供了兩種不同的自訂排序方式： 1. **`sort_unstable_by_key`**：類似於 Python 的 `key` 參數，您可以傳入一個函式來提取用於比較的鍵。 2. **`sort_unstable_by`**：類似於 Go 的比較函式，您可以傳入一個回傳 `Ordering`（一個包含 `Less`、`Equal` 和 `Greater` 三個值的枚舉）的函式。 ```rust #[derive(Debug, Eq, Ord, PartialEq, PartialOrd)] struct Person { name: String, age: u32, } fn main() { let mut people = vec![ Person { name: "Alice".to_string(), age: 30 }, Person { name: "Bob".to_string(), age: 25 }, Person { name: "Charlie".to_string(), age: 35 }, ]; // 1. 使用 sort_unstable_by_key 按年齡升序排序 people.sort_unstable_by_key(|p| p.age); println!("{:?}", people); // 2. 使用 sort_unstable_by 按年齡降序排序 people.sort_unstable_by(|a, b| b.age.cmp(&a.age)); println!("{:?}", people); } ``` **輸出結果：** ``` [Person { name: "Bob", age: 25 }, Person { name: "Alice", age: 30 }, Person { name: "Charlie", age: 35 }] [Person { name: "Charlie", age: 35 }, Person { name: "Alice", age: 30 }, Person { name: "Bob", age: 25 }] ``` ### 總結 | 語言 | 方法 | 回傳值 | | --- | --- | --- | | C++ | 比較函式 | `bool` | | Python | Key Function | 任何可比較的值 | | Go | 比較函式 | `-1`, `0`, `1` | | Rust | Key Function 或比較函式 | 任何可比較的值或 `Ordering` | 從以上比較可以看出，雖然排序是一個基本的功能，但不同的程式語言在 API 設計上卻有著不同的哲學和取捨。C++ 提供了最底層的控制，但也相對繁瑣；Python 則追求簡潔與易用性；Go 則採用了傳統的「三向比較」；而 Rust 則提供了最靈活的選擇，讓開發者可以根據自己的需求選擇最適合的方式。 希望這篇文章能幫助您更深入地了解不同程式語言在排序功能設計上的差異，並在未來的開發工作中，選擇最適合您需求的排序方式。

演算法的逆襲：為何 O(N log N) 的排序，有時竟能擊敗 O(N) 的雜湊？

***此篇文章由 Gemini AI 產生*** ### **演算法的逆襲：為何 O(N log N) 的排序，有時竟能擊敗 O(N) 的雜湊？** 身為一個程式開發者，我們對時間複雜度（Big O）可說是瞭若指掌。O(N) 通常優於 O(N log N)，這幾乎是我們優化程式碼時的金科玉律。但如果我告訴你，在某些情況下，一個 O(N log N) 的演算法，在實際執行時竟然能穩定地擊敗 O(N) 的對手，你會怎麼想？ 這不是天方夜譚，而是在 LeetCode、專案優化、甚至面試中都可能遇到的真實場景。今天，就讓我們透過一個經典問題「最長和諧子序列 (Longest Harmonious Subsequence)」，來一場跨越 C++ 和 Python 的效能對決，揭開理論與現實之間的迷霧。 #### **戰場設定：最長和諧子序列** 問題很簡單：給定一個整數陣列 `nums`，找到其中最長「和諧子序列」的長度。所謂和諧子序列，是指該子序列中最大值與最小值的差，剛好為 1。 例如，對於 `nums = [1, 3, 2, 2, 5, 2, 3, 7]`，其最長和諧子序列是 `[3, 2, 2, 2, 3]`，由 2 和 3 組成，長度為 5。 解決這個問題，有兩種經典的思路： 1. **排序 + 滑動窗口 (Sorting + Sliding Window):** 先將陣列排序，然後用兩個指針 `l` 和 `r` 遍歷一次，找出符合條件的最長區間。時間複雜度是 O(N log N)，主要瓶頸在排序。 2. **雜湊表計數 (Hash Map):** 用一個雜湊表（在 Python 中是 `dict` 或 `Counter`）來計算每個數字出現的頻率。然後遍歷雜湊表，找出 `x` 和 `x + 1` 的頻率總和的最大值。時間複雜度是 O(N)，因為只需要遍歷陣列一次。 理論上，雜湊表法 (O(N)) 應該完勝排序法 (O(N log N))。讓我們來實際測試一下。 ----- ### **第一戰：C++ 的意外結局** 在 C++ 的世界裡，我們用 `std::sort` 和 `std::unordered_map` 來實現這兩種方法。 **方法一：排序 + 滑動窗口 (O(N log N))** ```cpp #include #include #include class Solution { public: int findLHS(std::vector& nums) { std::ranges::sort(nums); int ans = 0; int l = 0; for (int r = 1; r < nums.size(); ++r) { while (nums[r] - nums[l] > 1) ++l; if (nums[r] - nums[l] == 1) ans = std::max(ans, r - l + 1); } return ans; } }; ``` **方法二：雜湊表 (O(N))** ```cpp #include #include #include class Solution { public: int findLHS(std::vector& nums) { std::unordered_map freq; for (int num : nums) ++freq[num]; int ans = 0; for (const auto& [num, count] : freq) if (freq.count(num + 1)) ans = std::max(ans, count + freq.at(num + 1)); return ans; } }; ``` **驚人的結果：** 在多數的 LeetCode 測試案例中，**排序法的執行時間竟然比雜湊表法要短！** 這完全違背了我們對 Big O 的直覺。為什麼？答案藏在硬體底層。 #### **解密 C++：當快取為王 (Cache is King)** ##### **1. 記憶體存取模式：循序 v.s. 隨機** * **排序法**在排序完成後，其滑動窗口的操作是**循序存取 (Sequential Access)** 一塊連續的記憶體。這對 CPU 快取（Cache）極度友好。當 CPU 讀取 `nums[i]` 時，它會聰明地將 `nums[i+1]`, `nums[i+2]` 等鄰近資料一併載入到飛快的 L1/L2 快取中。下一次的存取幾乎是零延遲，因為資料早已在手邊。 * **雜湊表法**則完全不同。`freq[num]` 和 `freq[num + 1]` 在記憶體中的位置是透過雜湊函數計算得出的，它們幾乎肯定是**隨機分散 (Random Access)** 的。這會導致大量的**快取未命中 (Cache Miss)**，CPU 不得不頻繁地從慢速的主記憶體 (RAM) 中去抓取資料，效能因此大打折扣。 ##### **2. 隱藏的常數開銷** Big O 符號忽略了常數因子。`unordered_map` 的每次操作都伴隨著不小的開銷： * **雜湊計算：** 需要時間。 * **碰撞處理：** 無法避免，會帶來額外尋找成本。 * **記憶體分配：** 每個鍵值對都可能需要一次動態記憶體分配，這比 `vector` 的整塊分配慢得多。 在 C++ 這種「貼近硬體」的語言中，演算法與硬體（特別是 CPU 快取）的互動方式，往往比單純的理論複雜度更能決定最終效能。在這裡，排序法贏在它優雅而高效的記憶體存取模式。 ----- ### **第二戰：Python 的情勢逆轉** 現在，我們將戰場轉移到 Python。 **方法一：排序 + 滑動窗口 (O(N log N))** ```python class Solution: def findLHS(self, nums: List[int]) -> int: nums.sort() l = 0 ans = 0 for r in range(len(nums)): while nums[r] - nums[l] > 1: l += 1 if nums[r] - nums[l] == 1: ans = max(ans, r - l + 1) return ans ``` **方法二：`Counter` 雜湊表 (O(N))** ```python from collections import Counter class Solution: def findLHS(self, nums: List[int]) -> int: freq = Counter(nums) ans = 0 for num, count in freq.items(): if num + 1 in freq: ans = max(ans, count + freq[num + 1]) return ans ``` **預料之中的結果：** 在 Python 環境下，**`Counter` 雜湊表法輕易地擊敗了排序法**，完美符合 Big O 的理論預期。 為什麼情勢完全逆轉了？答案在於 Python 的語言特性。 #### **解密 Python：直譯器的代價與 C 語言的捷徑** ##### **1. 直譯器的巨大開銷** Python 是直譯語言。在排序法的滑動窗口迴圈中，`nums[r] - nums[l]` 這樣一行簡單的程式碼，背後需要經過 Python 直譯器繁重的工作：物件類型檢查、查找、分派操作等。這個「直譯器開銷」施加在迴圈的每一步上，積少成多，成為了巨大的效能瓶頸。 ##### **2. C 語言實現的「超車道」** Python 的高效，秘訣在於其豐富的、由 C 語言實現的內建函式庫。 * **`Counter(nums)`** 這個操作，其核心的計數邏輯完全是在**高效的 C 語言層級**執行的。Python 直譯器僅僅是發起一個呼叫，然後 C 程式碼就在幕後以極高的速度完成了 O(N) 的計數工作。 * 這個方法巧妙地將最主要的計算壓力，從緩慢的 Python 迴圈轉移到了飛快的 C 語言底層。 在 Python 的世界裡，快取帶來的效益依然存在，但它已經**不足以抵銷直譯器本身的巨大開銷**。效能的瓶頸從「記憶體存取」轉變成了「直譯器速度」。因此，誰能最大限度地減少在 Python 層級的迴圈次數，誰就是贏家。 ----- ### **結論：我們學到了什麼？** 這場跨越 C++ 和 Python 的效能對決，給我們帶來了幾個深刻的啟示： 1. **Big O 是指南，而非聖經：** 它描述了演算法在規模趨於無窮大時的趨勢，但在特定規模和特定環境下，常數因子和硬體互動同樣重要。 2. **了解你的語言：** C++ 讓你更貼近硬體，記憶體模式至關重要。Python 則提供了高效的 C 語言「捷徑」，善用內建函式庫是優化的關鍵。 3. **快取意識：** 無論使用何種語言，寫出對 CPU 快取友好的程式碼，都是一個通用的優化方向。 4. **實測為王 (Profile Your Code):** 當效能成為瓶頸時，不要猜測，要用實際的效能分析工具來找出問題所在。 下一次，當你面對一個演算法選擇時，除了分析 Big O，不妨也思考一下：**我的程式碼，將在怎樣的硬體和語言環境下運行？** 這個問題，或許能引導你找到通往極致效能的真正路徑。

在 Rust 上又遇到了一次跟 C++ 一樣的問題

今天在練習 LeetCode [1498. Number of Subsequences That Satisfy the Given Sum Condition](https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/) 這題時，用 Rust 寫出了以下的程式碼。 ```rust impl Solution { pub fn num_subseq(mut nums: Vec<i32>, target: i32) -> i32 { let MOD = 1e9 as i32 + 7; let n = nums.len(); let mut pow2 = vec![1; n]; for i in 1..n { pow2[i] = (pow2[i-1] << 1) % MOD; } nums.sort(); let (mut l, mut r, mut count) = (0, n - 1, 0); while l <= r { if nums[l] + nums[r] <= target { count = (count + pow2[r-l]) % MOD; l += 1; } else { r -= 1; } } count } } ``` 心想說應該沒什麼問題吧，就用跟其他程式語言同樣的邏輯，再寫一遍就好了。 結果就撞到了跟上次 [C++ 的 std::string::size() 使用上要小心的地方](https://fourdollars.blogspot.com/2024/11/c-stdstringsize.html) 同樣的問題。 Orz r 在 0 之後變成了 usize 的最大值，然後就爆掉了。 應該要特地將 r 弄成 i32 才對，可是不覺得上面的程式碼看起來很順暢不是嗎？盡量少用 as，讓型別自動推導出來，然後就爆掉了，果然魔鬼都是藏在細節裡面。囧rz ```rust impl Solution { pub fn num_subseq(mut nums: Vec<i32>, target: i32) -> i32 { let MOD = 1e9 as i32 + 7; let n = nums.len(); let mut pow2 = vec![1; n]; for i in 1..n { pow2[i] = (pow2[i-1] << 1) % MOD; } nums.sort(); let (mut l, mut r, mut count) = (0, n as i32 - 1, 0); while l <= r { if nums[l as usize] + nums[r as usize] <= target { count = (count + pow2[(r-l) as usize]) % MOD; l += 1; } else { r -= 1; } } count } } ```

透過 BROWSER 環境變數在 headless server 上搞定 Gemini CLI 的 Google 登入

此篇文章由 Gemini AI 產生

嘿，各位開發者！如果你也嘗試在沒有圖形介面的伺服器上使用 npm install -g @google/gemini-cli，並希望透過 Google 帳號登入，你可能遇到了一個小麻煩：「沒有網址讓我連過去認證！」

別擔心，這篇文章將帶你一步步解決這個問題，讓你能在伺服器上順利使用 Gemini CLI。

問題根源：無頭環境的挑戰

當你在本地電腦使用 Google 登入時，CLI 會自動開啟瀏覽器讓你完成認證。但在伺服器這種「無頭 (headless)」環境，它根本沒辦法開啟瀏覽器。這導致了認證流程的中斷。

我們要做的，就是**「欺騙」CLI**，讓它以為有個瀏覽器會幫它處理網址，但實際上我們只是把認證網址攔截下來，然後手動到自己的電腦上完成登入。

步驟一：讓 CLI「吐出」認證網址

首先，我們需要一個簡單的 Shell 指令碼，來捕捉 Gemini CLI 嘗試開啟的認證網址。

1. 建立 url-logger.sh 指令碼：

   
   

   在你的伺服器上，建立一個新檔案，例如放在 /usr/local/bin/url-logger.sh。

   nano /usr/local/bin/url-logger.sh
   

   然後貼上以下內容：

   #!/bin/bash
   # 這個指令碼會將 Gemini CLI 嘗試開啟的網址記錄下來
   
   # 認證網址將被寫入這個檔案
   URL_FILE="$HOME/gemini_auth_url.txt"
   
   # 確保檔案存在
   touch "$URL_FILE"
   
   # 將網址和時間戳記附加到檔案中
   echo "$(date '+%Y-%m-%d %H:%M:%S') - $1" >> "$URL_FILE"
   
   # 同時印出到終端機，方便查看
   echo "URL would be opened: $1"
   

2. 賦予執行權限：

   讓這個指令碼可執行。

   chmod +x /usr/local/bin/url-logger.sh
   

步驟二：設定 BROWSER 環境變數

接下來，我們要告訴系統，當任何程式（包括 Gemini CLI）嘗試開啟瀏覽器時，都執行我們剛才建立的 url-logger.sh 指令碼。

1. 編輯你的 Shell 設定檔：

   這通常是 ~/.bashrc (如果你用 Bash) 或 ~/.zshrc (如果你用 Zsh)。

   # 例如：
   nano ~/.bashrc
   

2. 添加 BROWSER 環境變數：

   在檔案的任何位置，加入這行。請確保路徑是 url-logger.sh 的實際存放位置。

   export BROWSER=/usr/local/bin/url-logger.sh
   

3. 儲存並重新載入設定：

   儲存檔案後，執行 source ~/.bashrc (或 source ~/.zshrc)，或者直接關閉並重新開啟你的 SSH 連線，讓設定生效。

步驟三：啟動 Gemini CLI 並獲取認證網址

現在，萬事俱備！我們可以啟動 Gemini CLI 並開始認證流程了。

1. 啟動 Gemini CLI：

   gemini
   

   進入互動式介面後，輸入 /auth，然後選擇 "Login with Google"。

2. 檢查認證網址檔案：

   此時，gemini 不會開啟任何視窗，而是把認證網址寫入到我們指定的檔案中。你可以用 cat 命令查看：

   cat "$HOME/gemini_auth_url.txt"
   

   你會看到一串類似 https://accounts.google.com/o/oauth2/v2/auth?client_id=... 的超長網址。請完整複製這串網址！

步驟四：在本地電腦完成 Google 認證

現在，輪到你的本地電腦出場了！

1. 在本地瀏覽器開啟網址：

   把你剛才從伺服器上複製的完整認證網址，貼到你本地電腦的網頁瀏覽器中，然後打開它。

2. 完成 Google 登入和授權：

   按照 Google 頁面的指示，用你的 Google 帳號登入並授權。完成後，瀏覽器會嘗試跳轉到一個類似 http://localhost:PORT/oauth2callback?code=YOUR_CODE... 的網址。這個頁面會顯示「此網站無法連線」之類的錯誤，這是完全正常的！

步驟五：將 localhost 回調傳回伺服器

這是最關鍵的一步！我們要將本地瀏覽器嘗試跳轉的 localhost 網址（即使它報錯了），再傳回給伺服器上的 gemini CLI。

1. 複製 localhost 回調網址：

   從你本地瀏覽器的網址列上，完整複製那個 http://localhost:PORT/oauth2callback?... 的網址。務必包含所有的參數！

2. 在伺服器上執行 curl 命令：

   回到你的伺服器終端機，執行以下 curl 命令，將雙引號內的內容替換成你剛才複製的完整 localhost 網址：

       curl "http://localhost:YOUR_PORT/oauth2callback?code=YOUR_CODE&scope=..."
   

   例如：

   curl "http://localhost:21165/oauth2callback?code=4/0xxxxxxxxxxxxxxxxx&scope=https://www.googleapis.com/auth/userinfo.email..."
   

   執行完 curl 後，你會看到伺服器上的 gemini CLI 互動介面會顯示認證成功的訊息。恭喜你！

搞定！還有更好的選擇嗎？

你已經成功在無頭伺服器上搞定了 Gemini CLI 的 Google 帳號登入！這證明了只要掌握方法，多麼棘手的環境問題都能克服。

不過，對於長期或自動化用途，我仍然會強烈推薦使用服務帳戶 (Service Account) 進行認證。服務帳戶提供更高的安全性，而且完全不需要人工介入，對於伺服器應用來說是更優雅的解決方案。你可以參考官方文件或相關教學，了解如何建立和使用 Google Cloud 服務帳戶金鑰。

希望這篇文章對你有幫助！Happy coding!

以上內容由 Gemini AI 整理 Gemini CLI 伺服器設定指南 對話內容產出。