从链表中有效地选择一组随机元素

说我有一个长度数字的链表N.N非常大,我事先并不知道确切的价值N.

如何最有效地编写一个从列表中返回k完全随机数的函数？

使用称为储层采样的方法,有一种非常好的高效算法.

让我先介绍一下它的历史:

Knuth在p上调用此算法R. 他1997年版的"数字算法"(计算机程序设计艺术第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)概率的每个元素,为我们提供了归纳所必需的基本情况.

参考

McLeod,A.Ian和David R. Bellhouse."绘制简单随机样本的简便算法." 皇家统计学会期刊.C系列(应用统计学)32.2(1983):182-184.(链接)

Vitter,Jeffrey S."用水库随机抽样." ACM数学软件交易(TOMS)11.1(1985):37-57.(链接)

这称为储层采样问题.简单的解决方案是在您看到的时候为列表的每个元素分配一个随机数,然后保持按随机数排序的顶部(或底部)k元素.