水塘抽樣 水塘抽樣英語Reservoir sampling是一系列的隨機算法其目的在於從包含n個項目的集合S中選取k個樣本其中n為一很大或未知的數量尤其適用於不能把所有n個項目都存放到内存的情況最常見例子為Jeffrey Vitter英语Jeffrey Vitter在其論文中所提及的算法R 參照Dictionary of Algorithms and Data Structures所載的 O  n  displaystyle On 算法包含以下步驟假設数组S以開始標示 從S中抽取首k項放入水塘中 對於每一個Sj項j  k 隨機產生一個範圍從到j的整數r 若 r  k 則把水塘中的第r項換成Sj項