有一个非常好的且有效的算法，使用称为水库取样.
让我首先给你它history:
Knuth在 p 上调用该算法 R。他的 1997 年版《半数值算法》（《计算机编程艺术》第 2 卷）第 144 节，并在那里提供了一些代码。高德纳 (Knuth) 将算法归功于艾伦·G·沃特曼 (Alan G. Waterman)。尽管进行了长时间的搜索，我仍然无法找到 Waterman 的原始文档（如果存在），这可能就是为什么您最常看到 Knuth 被引用为该算法的来源。
麦克劳德和贝尔豪斯，1983(1) 提供了比 Knuth 更彻底的讨论以及该算法有效的第一个发布的证明（据我所知）。
维特 1985(2) 回顾算法 R，然后提出另外三种算法，它们提供相同的输出，但有所不同。他的算法不是选择包含或跳过每个传入元素，而是预先确定要跳过的传入元素的数量。在他的测试中（诚然，现在已经过时了），通过避免随机数生成和对每个传入数字的比较，大大减少了执行时间。
In 伪代码算法是：
Let R be the result array of size s
Let I be an input queue
> Fill the reservoir array
for j in the range [1,s]:
R[j]=I.pop()
elements_seen=s
while I is not empty:
elements_seen+=1
j=random(1,elements_seen) > This is inclusive
if j<=s:
R[j]=I.pop()
else:
I.pop()
请注意，我专门编写了代码以避免指定输入的大小。这是该算法的一个很酷的特性：您可以运行它而无需事先知道输入的大小still向您保证您遇到的每个元素都有相同的概率最终出现R（即没有偏见）。此外，R包含算法始终考虑的元素的公平且具有代表性的样本。这意味着您可以将其用作在线算法.
为什么这有效？
McLeod 和 Bellhouse (1983) 使用组合数学提供了证明。它很漂亮，但是在这里重建它会有点困难。因此，我生成了一个更容易解释的替代证明。
我们通过归纳法进行证明。
假设我们想要生成一组s元素以及我们已经看到的n>s元素。
假设我们当前的s每个元素都已被概率选择s/n.
根据算法的定义，我们选择元素n+1有概率s/(n+1).
已经属于结果集的每个元素都有一个概率1/s被替换。
一个元素从n-seen结果集被替换为n+1- 因此看到的结果集是(1/s)*s/(n+1)=1/(n+1)。反之，某个元素未被替换的概率为1-1/(n+1)=n/(n+1).
就这样n+1-seen 结果集包含一个元素，如果它是n- 看到结果集并且没有被替换---这个概率是(s/n)*n/(n+1)=s/(n+1)---或者如果选择了该元素---有概率s/(n+1).
算法的定义告诉我们，第一个s元素自动包含为第一个n=s结果集的成员。因此，n-seen结果集包含每个元素s/n(=1) 概率为我们提供了归纳所需的基本情况。
参考
麦克劳德、A. 伊恩和大卫 R. 贝尔豪斯。 “一种用于抽取简单随机样本的便捷算法。”皇家统计学会杂志。 C 系列（应用统计）32.2 (1983)：182-184。 (Link)
Vitter, Jeffrey S.“使用水库随机采样。” ACM 数学软件汇刊 (TOMS) 11.1 (1985)：37-57。 (Link)
