水塘抽樣是一系列的隨機算法。
基本介紹
- 中文名：水塘抽樣
- 屬性：隨機算法
- 目的：從n個項目的集合S中選取k個樣本
簡介,算法步驟,實例,
簡介
水塘抽樣是一系列的隨機算法，其目的在於從包含n個項目的集合S中選取k個樣本，其中n為一很大或未知的數量，尤其適用於不能把所有n個項目都存放到記憶體的情況。最常見例子為Jeffrey Vitter在其論文中所提及的算法R。
算法步驟
參照Dictionaryof 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，以Pn表示。如果檔案共有N行，任意第n行被抽取的機率為
故此，各行被抽取的機率均相同。
由於上述算法不需要先把整個檔案掃描以判定總行數再作抽樣，此算法是一線上算法。
以上問題可擴展為
- 可否在一未知大小的集合中，隨機取出k個元素？
亦即是說，如果檔案共有
行，則每一行被抽取的機率為
，則算法為
$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，以{\displaystyle Pn表示。如果檔案共有N行，任意第n行被抽取的機率為
