水塘抽樣

水塘抽樣（英語：Reservoir sampling）是一系列的隨機算法，其目的在於從包含n個項目的集合S中選取k個樣本，其中n為一很大或未知的數量，尤其適用於不能把所有n個項目都存放到内存的情況。最常見例子為Jeffrey Vitter（英语：Jeffrey Vitter）在其論文^[1]中所提及的算法R。

參照Dictionary of Algorithms and Data Structures^[2]所載的${\displaystyle O(n)}$算法，包含以下步驟（假設数组S以0開始標示）：

從S中抽取首k項放入「水塘」中 對於每一個S[j]項（j ≥ k）： 隨機產生一個範圍從0到j的整數r 若 r < k 則把水塘中的第r項換成S[j]項 

實例

在高德納的計算機程序設計藝術中，有如下問題：

可否在一未知大小的集合中，隨機取出一元素？

例如在一很大，但未知確實行數的文字檔中抽取任意一行。如果要確保每一行抽取的機率相等，即是說如果最後發現文字檔共有N行，則每一行被抽取的機率均為1/N，則有如下算法（以Perl表示）

$line; $n = 0; srand; while(<>) { $n++; $line = $_ if (rand < (1/$n)); } 

以下Perl程序為上述程序之精簡寫法：

srand; rand($.) < 1 && ($line = $_) while <>; 

上例中，在迴圈內第n行被抽取的機率為1/n，以${\displaystyle P_{n}}$ 表示。如果檔案共有N行，任意第n行被抽取的機率為

${\displaystyle {\begin{aligned}&P_{n}\prod _{k=n+1}^{N}(1-P_{k})\\=&{\frac {1}{n}}\prod _{k=n+1}^{N}(1-{\frac {1}{k}})\\=&{\frac {1}{n}}\prod _{k=n+1}^{N}{\frac {k-1}{k}}\\=&{\frac {1}{n}}{\frac {n}{n+1}}{\frac {n+1}{n+2}}\cdots {\frac {N-1}{N}}\\=&{\frac {1}{N}}\end{aligned}}}$ 

故此，各行被抽取的機率均相同。

由於上述算法不需要先把整個檔案掃描以判定總行數再作抽樣，此算法是一線上算法。

以上問題可擴展為

可否在一未知大小的集合中，隨機取出k個元素？

亦即是說，如果檔案共有${\displaystyle N\geq k}$ 行，則每一行被抽取的機率為${\displaystyle {\frac {k}{N}}}$ ，則算法為

$k = 輸出數量; @lines; $n = 0; srand; while(<>) { $n++; if ($n <= $k) { push(@lines, $_); } else { $r = int(rand($n)); if ($r < $k) { $lines[$r] = $_; } } } 

上例中，在迴圈內第n行被抽取的機率為k/n，以${\displaystyle P_{n}}$ 表示。如果檔案共有N行，任意第n行被抽取的機率為

${\displaystyle {\begin{aligned}&P_{n}\prod _{j=n+1}^{N}(1-{\frac {P_{j}}{k}})\\=&{\frac {k}{n}}\prod _{j=n+1}^{N}(1-{\frac {k}{kj}})\\=&{\frac {k}{n}}\prod _{j=n+1}^{N}{\frac {j-1}{j}}\\=&{\frac {k}{n}}{\frac {n}{n+1}}{\frac {n+1}{n+2}}\cdots {\frac {N-1}{N}}\\=&{\frac {k}{N}}\end{aligned}}}$ 

因此，各行被抽取的機率均相同。同理，此算法亦是線上算法。

在水塘算法的定義中，並沒有要求每一項目被抽取的機率相同，然而相同機率的情況較常用。

參考文獻

1. Jeffrey Scott Vitter. Random Sampling with a Reservoir (PDF). [2020-02-09]. （原始内容 (PDF)于2020-02-28） （英语）. 
2. reservoir sampling. [2020-02-09]. （原始内容于2018-10-13） （英语）.