水塘抽樣

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

參照Dictionary of Algorithms and Data Structures所載的$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，以$P_{n}$表示。如果檔案共有N行，任意第n行被抽取的概率為

${\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個元素？

亦即是說，如果檔案共有$N\geq k$行，則每一行被抽取的概率為${\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，以$P_{n}$表示。如果檔案共有N行，任意第n行被抽取的概率為

${\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}}$

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

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