水塘抽样

水塘抽样（英语：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}}$

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

在水塘算法的定义中，并没有要求每一项目被抽取的机率相同，然而相同机率的情况较常用。