從 LeetCode 3600 看工程思維：極致效能 vs 萬用架構

在面對演算法挑戰時，我們常常會陷入「尋求最快解」的迷思。然而，在真實世界的軟體工程中，最快的演算法真的永遠是最好的選擇嗎？

今天我們透過 LeetCode 3600: Maximize Spanning Tree Stability with Upgrades 這道經典的圖論題，來看看兩種截然不同的解題思路，以及它們在現實工業界中各自稱霸的真實場景。

題目背景：尋找最穩定的生成樹

這道題目的核心目標是：在給定的一張圖中，挑選出 $N-1$ 條邊形成「生成樹 (Spanning Tree)」。其中有些邊是「必選的」，有些是「可選的」。我們手上有 $K$ 次升級機會，可以將可選邊的強度乘以 2。 目標：最大化這棵樹的「最弱連結 (最小邊緣強度)」。

面對這個「最大化最小值」的難題，我們有兩種截然不同的解題策略。

策略一：二分搜尋 + 貪心驗證 (Binary Search on Answer)

這是一個非常扎實且通用的工程思維：我們不知道答案是多少，但我們可以「猜」。

運作邏輯：

1. 確定答案的上下界（例如強度從 $0$ 到 $100,000$）。

2. 猜測一個目標值 mid，並寫一個 check(mid) 函數來驗證：「在 $K$ 次升級內，我們能不能讓所有挑選的邊，強度都 $\ge mid$？」

3. 根據驗證結果，不斷縮小範圍，直到找到極限值。

💡 真實世界的應用場景：高擴充性的「萬用框架」

這個演算法雖然時間複雜度多了一個 $\log M$，但在真實的工程應用中，它卻具有壓倒性的擴充性 (Extensibility)！

• 電信網路的 SLA 保證與預算規劃 中華電信或 AWS 要牽線連接全球的資料中心，並保證最低可用頻寬。公司今年只給了預算購買 $K$ 台「訊號放大器」。網路架構師會透過這個演算法「二分猜測」保證頻寬，驗證預算是否足夠，藉此找出基礎建設的投資報酬率極限。

• EDA (電子設計自動化) 與晶片佈線 晶片設計中，工程師可以在線路上插入 Buffer（緩衝器）來增強訊號，但 Buffer 非常耗電且最多只能放 $K$ 個。軟體會猜測最差的訊號延遲時間，去驗證這 $K$ 個 Buffer 該怎麼放。

• 為什麼它無可取代？ 真實世界的規則往往不講武德。如果今天老闆說：「A 線路升級加 500、B 線路升級乘以 1.5、C 線路升級需要消耗 2 次升級機會...」純數學推導會瞬間崩潰，但二分搜尋版完全不受影響！你只需要在 check() 函數裡加上幾行 if-else，這個演算法就能完美存活。

策略二：Kruskal 演算法變形 (Pure Greedy)

這是一個將圖論數學性質發揮到極致的 $O(E \log E)$ 神級解法。它捨棄了「猜答案」，直接在一次遍歷中找出答案。

運作邏輯：

1. 將所有「可選邊」依照強度由大到小排序。

2. 依序將邊加入圖中（使用並查集 DSU 避免迴圈）。

3. 既然有 $K$ 次升級機會，為了讓「最小值」最大化，自然要把機會留給生成樹中最弱的那 $K$ 條邊。

4. 透過追蹤 edgesUsed，精準攔截出「沒有被升級的最弱邊」和「有被升級的最弱邊」，最後比較瓶頸即可。

💡 真實世界的應用場景：極致效能的「特製手術刀」

當規則明確且不變時，這種純貪心演算法能提供無與倫比的效能，特別適合底層系統與即時運算。

• Linux Kernel 的生成樹協定 (STP) 在網路橋接系統 (net/bridge/br_stp.c) 中，為了解決交換機之間的「廣播風暴」，Kernel 必須在極短時間內找出無迴圈的生成樹。Kruskal 演算法的底層邏輯正是這類網路防護機制的核心。

• 機器學習：層次分群 (Hierarchical Clustering) 在資料科學中 (例如 Single-linkage Clustering)，我們需要將特徵相近的資料點分群。背後運作完全依賴排序與並查集 (DSU)，能快速將距離最短的節點合併，達成自動分類。

• 電腦視覺：影像分割 (Image Segmentation) 讓電腦看懂照片中哪裡是人、哪裡是背景。演算法將像素當作節點，顏色差異當作邊，透過並查集在極短的 $O(1)$ 時間內將相似區塊合併，達成即時去背效果。

總結

LeetCode 3600 教會我們最重要的一課是：演算法沒有絕對的好壞，只有最適合的情境。

• 如果你面對的是一個規則單純、對效能要求極高的底層系統，請拿出 Kruskal 貪心法 這把特製手術刀。

• 如果你面對的是一個業務邏輯複雜、需求隨時會變更的商業系統，請架構好 二分搜尋驗證 這個萬用防護罩。

下次在解題時，不妨多想一步：這段程式碼如果放到真實世界，它會扮演什麼樣的角色呢？

修復 v4l2loopback 0.15.0 的 V4L2 緩衝區佇列問題

## 問題現象 使用 GStreamer v4l2sink 將影像送到 v4l2loopback 虛擬攝影機時出現錯誤： ``` WARN v4l2bufferpool: buffer X was not queued, this indicates a driver bug ``` 經過分析發現是 v4l2loopback 0.15.0 違反 V4L2 規格所致。 ## V4L2 緩衝區佇列規格 V4L2 規格定義的緩衝區使用流程： 1. **VIDIOC_REQBUFS** - 配置緩衝區 2. **VIDIOC_QBUF** - 將緩衝區排入驅動程式佇列 3. **VIDIOC_DQBUF** - 從驅動程式佇列取出緩衝區 核心規則：DQBUF 只能回傳先前透過 QBUF 排入的緩衝區。 正確流程：`QBUF → (處理) → DQBUF → QBUF → (處理) → DQBUF ...` v4l2loopback 0.15.0 的錯誤流程：`(預填充) → DQBUF → (自動循環) → DQBUF → (自動循環) → DQBUF ...` 錯誤點：完全不需要 QBUF，DQBUF 永遠有可用緩衝區。 ## v4l2loopback 0.15.0 的問題 ### prepare_buffer_queue() 預先填充佇列 ```c /* 原始碼 */ for (pos = 0; pos < count; ++pos) { bufd = &dev->buffers[pos]; if (list_empty(&bufd->list_head)) list_add_tail(&bufd->list_head, &dev->outbufs_list); } ``` 問題：所有緩衝區在配置後立即被加入輸出佇列，沒有經過 QBUF。 ### vidioc_dqbuf() 循環使用緩衝區 ```c /* 原始碼 */ bufd = list_first_entry_or_null(&dev->outbufs_list, ...); if (bufd) list_move_tail(&bufd->list_head, &dev->outbufs_list); ``` 問題：使用 `list_move_tail()` 將緩衝區移到佇列尾端，形成循環。 ### 違反規格的行為 1. 緩衝區未經 QBUF 就出現在輸出佇列 2. DQBUF 回傳從未排入的緩衝區 3. 緩衝區自動循環使用 實際流程：`DQBUF → DQBUF → DQBUF ...` (完全不需要 QBUF) ### GStreamer 的檢查 GStreamer v4l2bufferpool 會追蹤已排入的緩衝區。收到未排入的緩衝區時報錯： ``` WARN v4l2bufferpool: buffer X was not queued, this indicates a driver bug ``` 這是正確的行為，因為驅動程式確實違反了規格。 ## 修復方法 ### 修改 prepare_buffer_queue() 清空輸出佇列，不要預先填充： ```c /* 清空輸出佇列 */ list_for_each_entry_safe(bufd, n, &dev->outbufs_list, list_head) { list_del_init(&bufd->list_head); } /* 重設緩衝區狀態 */ for (pos = 0; pos < count; ++pos) { bufd = &dev->buffers[pos]; unset_flags(bufd->buffer.flags); dev->bufpos2index[pos % count] = bufd->buffer.index; } ``` ### 修改 vidioc_dqbuf() 移除緩衝區，不要循環使用： ```c bufd = list_first_entry_or_null(&dev->outbufs_list, ...); if (bufd) list_del_init(&bufd->list_head); /* 移除，不循環 */ ``` ### 修復後的行為 - 輸出佇列初始為空 - 緩衝區只在透過 QBUF 排入時才進入輸出佇列 - DQBUF 移除緩衝區，不循環使用 - 符合 V4L2 規格要求 ## 測試驗證 修復前： ```bash gst-launch-1.0 icamerasrc ! v4l2sink device=/dev/video0 # ERROR: buffer X was not queued, this indicates a driver bug ``` 修復後： ```bash gst-launch-1.0 icamerasrc ! v4l2sink device=/dev/video0 # 正常運作，無錯誤訊息 # Firefox/Chrome 可正常使用虛擬攝影機 ``` ## 技術細節 ### 為什麼原設計會預先填充？ v4l2loopback 作為虛擬裝置，可能想簡化緩衝區管理，確保永遠有可用緩衝區。但這違反了 V4L2 規格，與嚴格遵循規格的程式（如 GStreamer）不相容。 ### list_del_init vs list_move_tail - `list_del_init()`: 明確表示「緩衝區不在佇列中」 - `list_move_tail()`: 暗示「移到另一個位置」，語義模糊 使用 `list_del_init()` 讓緩衝區狀態更清楚。 ### 多執行緒考量 正確的緩衝區狀態追蹤在多執行緒環境下很重要，可避免競爭條件。 ## 參考資料 - V4L2 Buffer: https://www.kernel.org/doc/html/latest/userspace-api/media/v4l/buffer.html - VIDIOC_QBUF/DQBUF: https://www.kernel.org/doc/html/latest/userspace-api/media/v4l/vidioc-qbuf.html - V4L2 Streaming I/O: https://www.kernel.org/doc/html/latest/userspace-api/media/v4l/io.html - GStreamer v4l2bufferpool: https://gitlab.freedesktop.org/gstreamer/gstreamer/-/blob/main/subprojects/gst-plugins-good/sys/v4l2/gstv4l2bufferpool.c ## 上游貢獻 修補程式已提交至上游：https://github.com/v4l2loopback/v4l2loopback/pull/656 ## 結論 V4L2 緩衝區管理規格的核心原則： 1. 明確的狀態轉換：QBUF → DQBUF 2. 應用程式控制：由應用程式決定何時提供緩衝區 3. 可預測行為：嚴格遵循規格 當應用程式報告 "driver bug" 時，通常確實是驅動程式的問題。

解析位元運算公式 n & ~(((n + 1) & ~n) >> 1)

# 前言 在解決「尋找最小的 $x$ 使得 $x \lor (x + 1) = n$ 」這個問題時，我們得出了一個結論：對於奇數 $n$ ，答案是將 $n$ 的二進位表示中，「末尾連續的 1」序列裡最高位的那一個 `1` 修改為 `0`。 例如：如果 $n$ 的二進位是 `...01111`，我們目標是把它變成 `...00111`。 這個操作可以透過以下這行精簡的位元運算公式完成： ```cpp n & ~(((n + 1) & ~n) >> 1) ``` 這篇筆記旨在拆解這個複合表達式，逐步說明其工作原理。 --- # 公式拆解 這個公式可以分為三個主要步驟來理解，我們由內而外進行分析。 我們的目標 $n$ 範例設為 **23**，二進位表示為 `00010111`。 我們的目標是將末尾三個 `1` 中最左邊的那個（值為 4 的位元）關閉。 ## 步驟一：找出右邊數來第一個「0」的位置 **表達式核心：** `(n + 1) & ~n` 這是非常經典的位元操作技巧，用於定位最低位的 `0`。 1. **`n + 1` 的進位特性**： 當一個整數加 1 時，其二進位末尾所有的連續 `1` 都會因為進位而變成 `0`，直到遇到第一個 `0`，該位置會變成 `1`，進位停止。 * (23) = `00010111` * (24) = `00011000` (注意末尾三個 1 變成了 0，它們左邊的 0 變成了 1) 2. **`~n` 取反**： * `~n` = `11101000` 3. **`&` (AND) 運算**： 將上述兩個結果進行 AND 運算，只會保留同時為 `1` 的位元。 ``` 00011000 (n + 1) & 11101000 (~n) ---------------- 00001000 (結果為 8) ``` **小結**：這一步成功分離出了 從右側開始數第一個非 `1` 的位置。 ## 步驟二：鎖定目標位元（向右移位） **表達式：** `(步驟一的結果) >> 1` 我們在步驟一找到了第一個 `0` 的位置（在範例中是第 3 位，數值為 8）。 但我們的目標是修改這個 `0` 位置**右邊**的那一個 `1`（也就是末尾連續 `1` 序列的最高位）。 因此，我們將步驟一的結果向右移動一位： * `00001000 >> 1` = `00000100` (數值為 4) **小結**：這一步得到了一個「遮罩 (Mask)」，這個遮罩只有我們想要修改的那一個目標位元是 `1`，其他都是 `0`。 ## 步驟三：清除目標位元 **表達式：** `n & ~(步驟二的遮罩)` 現在我們有了目標遮罩 `Mask = 00000100`。我們要利用這個遮罩把 對應位置的 `1` 變成 `0`，並保持其他位置不變。 這是標準的「清除位元」操作： 1. **`~Mask` (遮罩取反)**： 製造一個工具，目標位置為 `0`，其他位置全為 `1`。 * `~Mask` = `11111011` 2. **`n & (~Mask)`**： 將原始的 與這個反向遮罩做 AND。 * 目標位置：`1 & 0` 結果為 `0`（成功清除）。 * 其他位置：`x & 1` 結果仍為 `x`（保持不變）。 ``` 00010111 (n, 即 23) & 11111011 (~Mask) ---------------- 00010011 (結果為 19) ``` # 總結 回顧整個流程： 1. `00010111` (原始 n) 2. `00001000` (找到第一個 0) 3. `00000100` (右移，鎖定目標 1) 4. `11111011` (取反，準備清除工具) 5. `00010011` (與原數 AND，完成清除) 這個公式 `n & ~(((n + 1) & ~n) >> 1)` 利用了加法進位的特性和基本的邏輯閘操作，在不使用任何迴圈的情況下，精確地完成了「關閉末尾連續 1 中最高位」的任務。這是一種高效且常見於底層優化的寫法。

在 Copilot CLI 使用 Spec Kit 流程圖

我把使用的大概細節跟過程記錄在 https://hackmd.io/@fourdollars/SpecKit 上面，用 feat: Add shared storage support for multi-unit Concourse CI deployments #5 這個 Pull Request 來練習完整走過整個流程，總共產生了 122 commits 跟 43 個檔案變更，過程有苦有樂也有辛酸，感覺在帶一個做事很快不會抱怨也很主動積極的新同事，但是就是要處處盯著他做事，幫他解決一些卡住的地方。

Concourse CI Machine Charm 是我正在開發的一個使用 Juju 快速架構管理維護 Concourse CI 服務的一套解決方案，已經可以從 edge channel 拿來使用了，不過還在開發中還有許多地方沒有完善，所以還沒有穩定釋出版本。

深入解析 grep 的「Broken pipe」錯誤：隨機出現的原因與優雅解法

最近我在 [ChromeOS Flex](https://chromeos.google/products/chromeos-flex/) 的 Linux 環境中使用 [Homebrew](https://brew.sh/) 時，總是會隨機看到 `grep: write error: Broken pipe`。後來去檢查相關程式碼，發現是這行 `grep -E "^(flags|Features)" /proc/cpuinfo | grep -q "ssse3"` 指令造成的。 這個錯誤雖然不一定影響最終結果，但在特定環境下出現總是讓人感到困惑。為什麼這行看似普通的管線指令會隨機報錯？今天就來深入探討其成因，並提供修正方案。 ## 「破裂的管線」錯誤成因 這個錯誤的核心，在於 Linux 作業系統處理**行程（Process）**與**管線（Pipe）**的機制。 當我們執行上述指令時，發生了以下連鎖反應： 1. **前端寫入（Producer）**： 第一個指令 `grep -E ...` 負責讀取 CPU 資訊，並持續將符合條件的資料寫入管線。 2. **後端讀取與提早退出（Consumer）**： 管線另一端的 `grep -q "ssse3"` 負責接收資料。關鍵在於 `-q` (quiet) 參數，它告訴 `grep` 一旦找到 "ssse3"，就**立即停止讀取並退出程式**。 3. **管線斷裂（Broken Pipe）**： 當後端 `grep` 退出後，管線的讀取端隨之關閉。然而，前端的 `grep` 此時可能還在嘗試寫入剩餘的資料。當它試圖寫入這條「已關閉」的管線時，系統便會發送 **SIGPIPE** 訊號，導致行程終止並印出 `write error: Broken pipe`。 ## 為何錯誤是隨機出現的？ 既然機制如此，為何不是「每次」都報錯？這歸因於**競爭條件（Race Condition）**。 電腦的排程器決定了兩個程式執行的快慢： * **沒事發生的情況**：前端 `grep` 產出資料的速度夠快，或者資料量剛好夠小，在後端退出前就已經寫完並結束了。 * **報錯的情況**：後端 `grep -q` 很快就找到了 "ssse3" 並關閉管線，而前端還來不及寫完剩下的資料，導致寫入失敗。 這種執行時間上的微小差異，決定了你是否會看到這行錯誤訊息。 ## 更優雅的解決方案 既然問題出在「多個指令透過管線傳輸」的時間差，最穩健的解法就是**避免使用管線**，將邏輯整合到單一 `grep` 指令中。 我們可以將原本的指令： ```bash grep -E "^(flags|Features)" /proc/cpuinfo | grep -q "ssse3" ``` 改寫為： ```bash grep -qE '^(flags|Features).*\bssse3\b' /proc/cpuinfo ``` ### 改寫後的優點： * **消除競爭條件**：單一行程運作，完全根除「管線破裂」的可能性。 * **效能提升**：省去了啟動兩個行程與建立管線的開銷。 * **精準度提高**： * `^(flags|Features)`：鎖定行首。 * `.*\bssse3\b`：利用 `\b`（單詞邊界）精確匹配 "ssse3"，避免誤判類似字串。 下次若在 Script 中發現類似的隨機管線錯誤，不妨檢查是否使用了會提早退出的指令（如 `grep -q`、`head` 等），並嘗試將其整合以提升穩定性！ 順便生了一個 [pull request](https://github.com/Homebrew/brew/pull/21366) 給 Homebrew

自幹了一個 Agent Skills - Launchpad Skill

放在 https://github.com/fourdollars/lp-api/ 專案底下的 launchpad 目錄底下，當然就是用 lp-api 這個小工具來串接。

我自己有在 OpenCode, GitHub Copilot CLI, Gemini CLI 上面成功掛載起來使用。

基本上就是把 AI Agent 接上 Launchpad，用自然語言去叫 AI 做自己想要做的事情。

以下是幾張 OpenCode 上使用的示範。

有興趣的人可以去看看 Agent Skills 了解一下。

Kadane's algorithm

昨天練習的題目是 3381. Maximum Subarray Sum With Length Divisible by K，題目的最佳解是利用 Kadane's algorithm，我覺得比較容易理解的方式是先計算前面 k-1 個 kSum 之後，再往後面用 Kadane's algorithm 來解。

如果是寫 C++ 是這樣：

class Solution {
public:
    long long maxSubarraySum(vector< int>& nums, int k) {
        const int n = nums.size();
        vector< long long> kSum(k, 0);
        long long maxSum = numeric_limits< long long>::min(), prefixSum = 0;
        for (int i = 0; i < k - 1; ++i) {
            prefixSum += nums[i];
            kSum[i] = prefixSum;
        }
        for (int i = k - 1; i < n; ++i) {
            prefixSum += nums[i];
            int r = i % k;
            maxSum = max(maxSum, prefixSum - kSum[r]);
            kSum[r] = min(kSum[r], prefixSum);
        }
        return maxSum;
    }
};

寫 Python3 是這樣：

class Solution:
    def maxSubarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        kSum = [0] * k
        prefixSum = 0
        maxSum = float("-inf")
        for i in range(k - 1):
            prefixSum += nums[i]
            kSum[i] = prefixSum
        for i in range(k - 1, n):
            prefixSum += nums[i]
            r = i % k
            maxSum = max(maxSum, prefixSum - kSum[r])
            kSum[r] = min(kSum[r], prefixSum)
        return maxSum

寫 Go 是這樣，這邊要注意即便是使用 math.MinInt64 還是要用 int64() 明確轉型，不然預設會用 int 然後就會跟後面的 int64 衝突。

func maxSubarraySum(nums []int, k int) int64 {
	n := len(nums)
	kSum := make([]int64, k)
	prefixSum, maxSum := int64(0), int64(math.MinInt64)
	for i := range n {
		prefixSum += int64(nums[i])
		if i < k-1 {
			kSum[i] = prefixSum
			continue
		}
		r := i % k
		maxSum = max(maxSum, prefixSum-kSum[r])
		kSum[r] = min(kSum[r], prefixSum)
	}
	return maxSum
}

寫 Rust 是這樣，沒什麼特別要注意的地方，反正寫錯時編譯器會提醒你該如何修正。 :-P

impl Solution {
    pub fn max_subarray_sum(nums: Vec< i32>, k: i32) -> i64 {
        let k = k as usize;
        let n = nums.len();
        let mut kSum = vec![0i64; k];
        let mut prefixSum = 0i64;
        let mut maxSum = i64::MIN;
        for i in 0..(k-1) {
            prefixSum += nums[i] as i64;
            kSum[i] = prefixSum;
        }
        for i in (k-1)..n {
            prefixSum += nums[i] as i64;
            let r = i % k;
            maxSum = maxSum.max(prefixSum - kSum[r]);
            kSum[r] = kSum[r].min(prefixSum);
        }
        maxSum
    }
}

不曉得為何，寫 Rust 有最愉快的感覺。 :-P