查看“︁水塘抽樣”︁的源代码

{{noteTA
|G1=IT
|1=zh-hk:水塘;zh-cn:蓄水池;
}}
'''水塘抽樣'''（{{lang-en|Reservoir sampling}}）是一系列的[[随机化算法|隨機算法]]，其目的在於從包含''n''個項目的集合''S''中選取''k''個樣本，其中''n''為一很大或未知的數量，尤其適用於不能把所有''n''個項目都存放到内存的情況。最常見例子為{{tsl|en|Jeffrey Vitter|Jeffrey Vitter}}在其論文<ref>{{Cite web |url=https://www.cs.umd.edu/~samir/498/vitter.pdf |title=Random Sampling with a Reservoir |author=Jeffrey Scott Vitter |accessdate=2020-02-09 |language=en |archive-date=2020-02-28 |archive-url=https://web.archive.org/web/20200228082119/http://www.cs.umd.edu/~samir/498/vitter.pdf |dead-url=no }}</ref>中所提及的''算法R''。

參照''Dictionary of Algorithms and Data Structures''<ref>{{Cite web |url=https://xlinux.nist.gov/dads/HTML/reservoirSampling.html |title=reservoir sampling |accessdate=2020-02-09 |language=en |archive-date=2018-10-13 |archive-url=https://web.archive.org/web/20181013022818/https://xlinux.nist.gov/dads/HTML/reservoirSampling.html |dead-url=no }}</ref>所載的<math>O(n)</math>算法，包含以下步驟（假設数组''S''以0開始標示）：

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

==實例==
在[[高德納]]的[[計算機程序設計藝術]]中，有如下問題：
:可否在一未知大小的集合中，隨機取出一元素？
例如在一很大，但未知確實行數的文字檔中抽取任意一行。如果要確保每一行抽取的機率相等，即是說如果最後發現文字檔共有''N''行，則每一行被抽取的機率均為''1/N''，則有如下算法（以Perl表示）

<syntaxhighlight lang=perl>
$line;
$n = 0;
srand;
while(<>) {
    $n++;
    $line = $_ if (rand < (1/$n));
}
</syntaxhighlight>
以下Perl程序為上述程序之精簡寫法：
<syntaxhighlight lang=perl>
srand;
rand($.) < 1 && ($line = $_) while <>;
</syntaxhighlight>
上例中，在迴圈內第''n''行被抽取的機率為''1/n''，以<math>P_n</math>表示。如果檔案共有''N''行，任意第n行被抽取的機率為
:<math>\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}</math>
故此，各行被抽取的機率均相同。

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

以上問題可擴展為
:可否在一未知大小的集合中，隨機取出k個元素？
亦即是說，如果檔案共有<math>N \ge k</math>行，則每一行被抽取的機率為<math>\frac{k}{N}</math>，則算法為
<syntaxhighlight lang=perl>
$k = 輸出數量;
@lines;
$n = 0;
srand;
while(<>) {
    $n++;
    if ($n <= $k) {
        push(@lines, $_);
    } else {
        $r = int(rand($n));
        if ($r < $k) {
            $lines[$r] = $_;
        }
    }
}
</syntaxhighlight>
上例中，在迴圈內第''n''行被抽取的機率為''k/n''，以<math>P_n</math>表示。如果檔案共有''N''行，任意第n行被抽取的機率為
:<math>\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}</math>
因此，各行被抽取的機率均相同。同理，此算法亦是線上算法。

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

== 參考文獻 ==
{{reflist|2}}

[[Category:隨機性]]
[[Category:演算法]]
[[Category:算法分析]]