有一种非常好的，高效的算法，可以使用称为 储层采样 的方法。

让我开始给你它的 历史 ：

Knuth 在p上将此算法称为R。他的1997年版的Seminumerical
Algorithms（计算机编程艺术的第2卷）第144页，并在那里提供了一些代码。Knuth将算法归因于Alan G.
Waterman。尽管进行了冗长的搜索，但我仍然找不到Waterman的原始文档（如果存在），这也许就是为什么您经常看到引用Knuth作为该算法的来源的原因。

McLeod和Bellhouse，1983年 （1）提供了比Knuth更为详尽的讨论，并提供了该算法有效的第一个公开证明（据我所知）。

Vitter 1985
（2）回顾了算法R，然后提出了另外三种算法，它们提供相同的输出，但又有所不同。他的算法不是选择包含还是跳过每个传入元素，而是预先确定要跳过的传入元素的数量。在他的测试中（现在已经过时了），这避免了随机数的产生和每个传入数字的比较，从而大大减少了执行时间。

用 伪代码 算法是：

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()

请注意，我专门编写了代码，以避免指定输入的大小。那是该算法的一个很酷的特性：您可以运行它而无需事先知道输入的大小，并且它 仍然可以
确保您遇到的每个元素都有相同的出现概率R（也就是说，没有偏差）
）。此外，R包含算法始终考虑的元素的公平且具有代表性的样本。这意味着您可以将其用作在线算法。

为什么这样做？

McLeod和Bellhouse（1983）使用组合数学提供了证明。很漂亮，但是在这里重建它有点困难。因此，我生成了一个更容易解释的替代证明。

我们通过归纳证明进行。

假设我们要生成一组s元素，并且已经看到了n>s元素。

假设我们当前的s每个元素都已经被概率选择了s/n。

根据算法的定义，我们选择n+1具有概率的元素s/(n+1)。

已经成为结果集一部分的每个元素都有1/s被替换的可能性。

因此，将n-seen结果集中的元素替换为n+1-seen结果集中的概率(1/s)*s/(n+1)=1/(n+1)。相反，不替换元素的概率为1-1/(n+1)=n/(n+1)。

因此，n+1-seen结果集包含一个元素，如果它是n-seen结果集的一部分并且未被替换-（此概率为(s/n)*n/(n+1)=s/(n+1)-或如果选择了元素）-被概率s/(n+1)。

该算法的定义告诉我们，第一个s元素会自动包含为n=s结果集的第一个成员。因此，n-seen结果集包括具有s/n（=
1）概率的每个元素，为我们提供了归纳的必要基本情况​​。

参考资料

1. McLeod，A。Ian和David R. Bellhouse。“一种用于绘制简单随机样本的便捷算法。” 皇家统计学会杂志。系列C（应用统计）32.2（1983）：182-184。（链接）

2. Vitter，JeffreyS。“使用水库进行随机采样。” ACM Transactions on Mathematical Software（TOMS）11.1（1985）：37-57。（链接）