雲端 Mac 上驗收 iOS 蓄水池取樣：可控亂數與窮舉驗證

在 Windows 上寫好日誌篩選功能後，需要從數量未知的事件串流中隨機保留少量紀錄。若將所有紀錄讀進陣列再打亂，記憶體用量就會隨輸入量成長。在雲端 Mac 上，可以先用 Swift 驗收蓄水池取樣，再將同一份實作接入 iOS 專案。關鍵不在於觀察結果「看起來夠不夠隨機」，而是將選取規則轉化為可重複驗證的契約。

確立取樣單位與容量契約

本文採用 Algorithm R：先保留前 k 項；讀到第 t 項時，從零到 t−1 均勻抽出整數 j，僅在 j 小於 k 時替換對應槽位。走訪結束後，每個輸入位置被選中的機率都是 k/n，額外儲存空間為 O(k)，走訪耗時為 O(n)。

這項結論的前提是：每一步抽取在給定先前歷程的條件下，仍然保持均勻分布。僅讓亂數落在正確範圍內，並不足以保證公平。

先約定四項邊界行為：容量不可為負；容量為零時回傳空樣本，且不消耗輸入；輸入項目少於容量時全部保留；重複值依不同位置分別參與取樣。輸出槽位的順序不是隨機排列，也不保證維持原始順序。

取樣公平不代表每次結果都不同。若將「連續兩次結果不可相同」寫進測試，就會把正常的隨機結果變成偶發性失敗。

將亂數來源與選取邏輯分離

登入 OSXMesh 雲端 Mac 後，在終端機執行 xcrun swift --version，確認目前的工具鏈能夠執行 Swift。將下列程式碼儲存為 ReservoirCheck.swift。閉包接收不包含在抽取範圍內的上限，讓正式環境的亂數來源與測試腳本共用同一套選取邏輯。

func reservoir<S: Sequence>(
    _ input: S,
    capacity: Int,
    draw: (Int) -> Int
) -> [S.Element] {
    precondition(capacity >= 0)
    guard capacity > 0 else { return [] }

    var sample: [S.Element] = []
    var seen = 0

    for value in input {
        seen += 1
        if sample.count < capacity {
            sample.append(value)
        } else {
            let slot = draw(seen)
            precondition(slot >= 0 && slot < seen)
            if slot < capacity {
                sample[slot] = value
            }
        }
    }
    return sample
}

let empty = reservoir([Int](), capacity: 2) { _ in
    preconditionFailure("Unexpected draw")
}
precondition(empty.isEmpty)

let zero = reservoir([1, 2], capacity: 0) { _ in
    preconditionFailure("Unexpected draw")
}
precondition(zero.isEmpty)

let short = reservoir([1, 2], capacity: 3) { _ in
    preconditionFailure("Unexpected draw")
}
precondition(short == [1, 2])

var counts: [String: Int] = [:]

for first in 0..<3 {
    for second in 0..<4 {
        var script = [first, second].makeIterator()
        var bounds: [Int] = []

        let sample = reservoir(0..<4, capacity: 2) { upper in
            bounds.append(upper)
            guard let next = script.next() else {
                preconditionFailure("Draw script exhausted")
            }
            return next
        }

        precondition(bounds == [3, 4])
        precondition(script.next() == nil)
        precondition(sample.count == 2)
        precondition(Set(sample).count == 2)

        let key = sample.sorted().map { String($0) }
            .joined(separator: ",")
        counts[key, default: 0] += 1
    }
}

let expected = ["0,1", "0,2", "0,3", "1,2", "1,3", "2,3"]
precondition(Set(counts.keys) == Set(expected))
precondition(counts.values.allSatisfy { $0 == 2 })

執行 xcrun swift ReservoirCheck.swift。檢查通過時不會輸出內容，失敗時則以非零狀態結束。腳本使用前置條件檢查，不應搭配會停用安全檢查的最佳化選項執行。實際應用若接受外部傳入的容量參數，應先驗證再呼叫演算法，而不是讓無效輸入導致程序終止。

窮舉十二條路徑驗證選取規則

從四個候選位置中選取兩個，第三項對應三種選擇，第四項對應四種選擇，因此共有十二條路徑。在上述亂數來源假設下，每條路徑的機率均為十二分之一，六個不計順序的位置組合應各出現兩次。

這裡檢查的是組合分布，而不只是個別位置出現的次數。某些錯誤實作可能讓每一項的邊際頻率接近一致，卻始終漏掉部分組合。

腳本也會核對亂數來源收到的上限必須依序為三和四，並確認預設的抽取序列恰好用完。少呼叫一次、多呼叫一次，或誤將上限寫成目前槽位數，都會使檢查失敗。排序只用來產生比較用的鍵值，不應暗中改變正式函式的回傳契約。

這個規模能抓出常見的替換條件錯誤，但不是適用於任意輸入規模的數學證明。合併前仍須審查歸納條件，並針對其他小規模容量補上窮舉測試案例。

涵蓋重複值與串流輸入的陷阱

測試重複值時，應使用帶有唯一序號的紀錄。例如，將兩個內容相同的事件分別標記為位置零和位置一，斷言被選中的位置不重複，而不能單純斷言樣本中的業務值皆不重複。先去除重複值再取樣，會改變各類事件的權重，也會增加儲存空間需求。

容量為一時，應分別強制走過替換與略過的情況；容量等於輸入長度時，不應呼叫亂數來源；容量大於輸入長度時，輸出長度應等於輸入長度。

針對只能消耗一次的序列，還應加上一個會統計讀取次數的迭代器。容量為零時，讀取次數必須為零；容量為正時，只能走訪一次。不要為了預先取得長度而呼叫 Array(input)，否則即使選取結果正確，也已違背串流處理的記憶體目標。

計數器也要求輸入項目數必須能以 Int 表示。對於沒有終點的事件串流，應以視窗結束作為取樣終點，不能期待這個同步函式自行回傳；取消與視窗關閉應由上層控制。

接入專案時保留可重現的證據

正式環境中可使用 Int.random(in: 0..<upper) 提供整數，不要對隨機整數取餘數來湊出範圍，也不要將固定的測試抽取序列帶入正式功能。這裡的取樣適用於一般資料處理，不應直接用來承擔安全抽籤的職責。

將腳本一併提交至版本庫，在雲端 Mac 的建置步驟中先執行腳本，再執行專案測試。每次失敗至少應保留輸入位置、容量、抽取序列與工具鏈版本；不要為了除錯而記錄真實使用者的事件本文。

最後，將驗收分成三層：確定性的邊界測試案例、小規模路徑窮舉，以及獨立的統計觀察。統計觀察適合用來發現亂數來源的串接異常，不宜用過窄的頻率門檻阻擋每次提交。迴歸測試應以明確、可重播的失敗路徑為依據，而不是因為某次取樣結果恰好不符合直覺。

常見問題