取樣演算法 — Reservoir Sampling（基本 R + 加權 A-Res）/ Alias Method（別名表 O(1) 抽樣）

很多時候我們留不住全部資料，只想公平地「抽幾筆當代表」——像廣播節目整天湧入無數通聽眾來電，主持人手上只有三個中獎名額，怎麼讓每一通機會都一樣？Reservoir Sampling（蓄水池抽樣）專治這種「邊來邊丟、總量還不知道」的串流，資料掃一遍就當場決定去留；Alias Method（別名表）則反過來——當各選項中獎率不一樣、又要反覆抽上幾萬次時，先花點工夫做一張表，之後每抽一次都快到 O(1)。下面你會看到兩者實際抽出的樣本，以及重跑很多次後，頻率是否真的收斂到理論值。

兩者都是把「依機率抽出代表性樣本」拆成不同前提下的最佳策略：Reservoir Sampling 面對的是總量未知、只能逐項掃過一次的串流，靠決定性偽隨機決策（擲骰決定要不要替換）維持固定大小 k 的等機率（或依權重）樣本；加權版 A-Res 為每項算出 key = u^(1/w)，取 key 最大的 k 項，讓權重大的項傾向更容易入選。 Alias Method 面對的則是總量已知的離散分佈，先花一次 O(n) 建表換取之後每次抽樣只需 O(1)（擲欄 + 比較門檻），適合需要重複大量抽樣的場景。本頁同時揭露「單一種子的一次結果」與「多種子重跑的統計頻率」，誠實對照頻率是否收斂到理論值，以及有限次數重跑時的波動。

為什麼 AI 時代重要

LLM 解碼時的 top-k/top-p（nucleus）取樣，本質上就是「依機率權重從候選 token 中抽一個」——與 Alias Method 要解決的問題完全相同（已知離散分佈、需要每個生成步驟重複高頻抽樣，O(1) 抽樣至關重要）；訓練資料清洗常需要依來源／品質權重混合多個資料集（例如某資料集權重調高兩倍），同樣是加權抽樣問題（Reservoir 的加權版 A-Res）；線上服務的請求日誌、即時對話紀錄等串流資料量無限成長、無法全部存下，只能像 Reservoir Sampling 這樣邊看邊決策，用固定大小的樣本代表整個串流（A/B 流量抽樣、線上日誌抽樣）。

它是隨機化演算法（QuickSelect）的延伸

QuickSelect 靠隨機 pivot 把選第 k 小的期望時間壓到 O(n)；Reservoir Sampling 與 Alias Method 同樣仰賴決定性 LCG 產生的偽隨機決策（擲骰決定要不要替換槽位、擲欄位決定抽哪一欄），但目標從「選出第 k 小」換成「維持代表性樣本」與「依機率分佈做 O(1) 抽樣」——三者同屬「用（偽）隨機性換取效率或空間」的隨機化演算法家族 → 雜項 Nim/折半列舉/QuickSelect/Mo's

1. Reservoir Sampling（基本 Algorithm R + 加權 A-Res）

基本 Algorithm R：串流前 k 項直接放入蓄水池；第 i 項（i>=k）擲 j = randInt(0..i)（含 i）， j < k 則以本項取代第 j 槽，否則捨棄——每項終態入選機率皆為 k/n。加權版 A-Res：每項取 u∈[0,1)，算 key = u^(1/w)，依 key 降冪取前 k 大者入選，權重愈大 1/w 愈小、key 傾向愈接近 1，入選機率隨權重上升，但屬「方向性」關係而非精確線性比例。兩者皆用 LCG next(x) = (1664525·x + 1013904223) mod 2^32、取值一律用高 16 位，並先 burn-in 3 步消除小種子單步高位窄帶偽影。

固定串流：[10,20,30,40,50,60,70,80]（n=8，蓄水池 k=3）；單一決策軌跡 seed=42；多種子頻率枚舉 seed=0..199（共 200 次）。加權項目 A(w=1)/B(w=2)/C(w=4)/D(w=8)，A-Res 入選 k=2；多種子頻率枚舉 seed=0..1999（共 2000 次，理由見下方誠實揭露）。

已決策數（decisions）：0 階段：reservoir

基本 R 段：列 0 = 串流值（固定不變）、列 1 = 蓄水池槽位（k=3，非槽位或尚未填入的欄位皆為空）。 A-Res 段：列 0 = label(w=權重)、列 1 = 目前 key 值。藍色外框（active）= 當前處理項；粉紅（pivot）= 被填入／替換的槽位，或本次計算 key 的項。 誠實揭露：seed=42 單一種子決策軌跡的終選結果只反映該次 u 的運氣，並非「權重排序保證」；多種子頻率是有限次數（200 / 2000）重跑的統計量，存在抽樣波動，不會與理論值精確相等； A-Res 只驗證「權重大 → 入選頻率高」的方向性，不宣稱頻率與權重成線性比例（精確機率涉及聯合分佈）； A-Res 原規劃與基本 R 一樣重跑 200 種子，但實測發現 A(w=1)/B(w=2) 兩項頻率因二項噪音而反轉（A=0.225 > B=0.21），故改用 2000 種子重跑消除此雜訊——是誠實調整，不是湊數。

單種子決策軌跡（seed=42，opLog）

（空）

200 種子頻率 vs 理論 k/n=0.375

串流值	頻率	理論	差值

A-Res keys（逐項累積）

A-Res 2000 種子頻率 vs 解析理論

項目	頻率	解析理論	差值

2. Alias Method（別名表法，Vose 演算法）

建表（Vose 演算法）：scaled_i = (w_i/Σw)·n，scaled_i < 1 者入 small 佇列，否則入 large 佇列；每輪由兩佇列各取一項 less/more：prob[less] = scaled[less]、alias[less] = more，再依 more 扣除補足量後的值歸回 small 或 large，直到一列清空，剩餘一列逐項定 prob = 1。建表完成後每次抽樣只需擲欄 col∈[0,n) 與擲 u∈[0,1)：u < prob[col] 選 col，否則選 alias[col]，恆為 O(1)，不隨 n 增長。

固定權重 [5,3,2]（理論分佈 p=[0.5,0.3,0.2]，n=3）；抽樣 seed=42，共抽 200 次（前 10 次逐次展開示範，其餘 190 次決策邏輯相同，彙總為一幀不逐次展開）。

已抽樣次數（draws）：0 階段：build

建表段（build）：列 0 = scaled 值、列 1 = prob 值、列 2 = alias 值（未定為空）。抽樣段（draw）：列 0 = 終表 prob 值、列 1 = 終表 alias 值；藍色外框（active）= 本次擲中的欄位，粉紅（pivot）= 最終選中的欄位（擲中欄與選中欄相同時只標粉紅）。O(1) 抽樣：建表一次 O(n) 換取之後每次抽樣只需擲欄 + 比較門檻，不隨 n 增長；前 10 抽逐次展開示範決策邏輯，其餘 190 抽邏輯相同、彙總為一幀不重複展開。200 抽頻率是有限次數重跑的統計量，與理論分佈 [0.5,0.3,0.2] 存在波動，屬正常現象，非精確相等。

別名表（prob / alias）

已執行操作紀錄（opLog）

（空）

200 抽頻率 vs 理論 [0.5,0.3,0.2]

項目	頻率	理論	差值

取樣演算法（Reservoir Sampling + Alias Method）