水塘抽樣

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

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

從S中抽取首k項放入「水塘」中
對於每一個S[j]項（j ≥ k）：
隨機產生一個範圍從0到j的整數r
若 r
$line;
$n = 0;
srand;
while(<>) {
$n++;
$line = $_ if (rand
以下Perl程序為上述程序之精簡寫法：

srand;
rand($.) ;

上例中，在迴圈內第n行被抽取的機率為1/n，以P_n表示。如果檔案共有N行，任意第n行被抽取的機率為
:\begin{align}
&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{align}
故此，各行被抽取的機率均相同。

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

以上問題可擴展為
:可否在一未知大小的集合中，隨機取出k個元素？
亦即是說，如果檔案共有N \ge k行，則每一行被抽取的機率為\frac{k}{N}，則算法為

$k = 輸出數量;
@lines;
$n = 0;
srand;
while(<>) {
$n++;
if ($n
上例中，在迴圈內第n行被抽取的機率為k/n，以P_n表示。如果檔案共有N行，任意第n行被抽取的機率為
:\begin{align}
&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{align}
因此，各行被抽取的機率均相同。同理，此算法亦是線上算法。

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

參考文獻