水塘抽样
2020-08-03 00:53:36
水塘抽样（英语：Reservoir sampling）是一系列的随机算法，其目的在于从包含个项目的集合中选取个样本，其中为一很大或未知的数量，尤其适用于不能把所有个项目都存放到内存的情况。最常见例子为Jeffrey Vitter（英语：Jeffrey Vitter）在其论文中所提及的。
引用所载的以0开始标示）：
從S中抽取首k項放入「水塘」中對於每一個S項（j ≥ k）： 隨機產生一個範圍從0到j的整數r 若 r < k 則把水塘中的第r項換成S項
实例
在高德纳的计算机程序设计艺术中，有如下问题：
例如在一很大，但未知确实行数的文字档中抽取任意一行。如果要确保每一行抽取的几率相等，即是说如果最后发现文字档共有行，则每一行被抽取的几率均为，则有如下算法（以Perl表示）
$line;$n = 0;srand;while(<>) { $n++; $line = $_ if (rand < (1/$n));}以下Perl程序为上述程序之精简写法：
srand;rand($.) < 1 && ($line = $_) while <>;
上例中，在循环内第行被抽取的几率为，以行，任意第n行被抽取的几率为
故此，各行被抽取的几率均相同。
由于上述算法不需要先把整个文件扫描以判定总行数再作抽样，此算法是一在线算法。
以上问题可扩展为
亦即是说，如果文件共有行被抽取的几率为，以行，任意第n行被抽取的几率为
因此，各行被抽取的几率均相同。同理，此算法亦是在线算法。
在水塘算法的定义中，并没有要求每一项目被抽取的几率相同，然而相同几率的情况较常用。