关于算法：从链表中有效选择一组随机元素

Efficiently selecting a set of random elements from a linked list

假设我有一个长度为N的数字链接列表。 N很大，我事先不知道N的确切值。

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

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

首先，我向您介绍它的历史：

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

McLeod和Bellhouse，1983年(1)提供了比Knuth更为全面的讨论，以及该算法有效的第一个公开证明(据我所知)。

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

用伪代码算法是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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进行了选择。

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

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

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

因此，n+1看到的结果集包含一个元素，如果它是n看到的结果集的一部分并且未被替换--此概率为(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，JeffreyS。"使用水库进行随机采样。" ACM Transactions on Mathematical Software(TOMS)11.1(1985)：37-57。 (链接)

这称为水库采样问题。一种简单的解决方案是为列表中的每个元素分配一个随机数，如您所见，然后按照随机数的顺序保留前(或后)k个元素。

我建议：首先找到您的k个随机数。对它们进行排序。然后遍历链接列表和您的随机数一次。

如果您不知道链表的长度(如何？)，则可以将第一个k捕获到数组中，然后对于节点r，在[0，r)中生成一个随机数，如果小于大于k，请替换数组的第r个项目。 (不完全相信这不会产生偏见...)

除此之外："如果我是你，我不会从这里开始。"您确定链接列表适合您的问题吗？是否没有更好的数据结构，例如好的旧式平面数组列表。

如果您不知道列表的长度，则必须遍历整个列表以确保随机选择。我在这种情况下使用的方法是Tom Hawtin(54070)描述的方法。在遍历列表时，您会保留k个构成随机选择的元素。 (最初，您只添加遇到的前一个k元素。)然后，用概率k/i，用列表中的第i个元素(即，您所在的位置，那一刻)。

很容易证明这给出了一个随机选择。看到m个元素(m > k)之后，我们发现列表中的每个前m个元素都是随机选择的一部分，概率为k/m。这最初是微不足道的。然后，对于每个元素m+1，将其以概率k/(m+1)放入选择中(替换随机元素)。现在，您需要证明所有其他元素也具有被选择的概率k/(m+1)。我们认为概率为k/m * (k/(m+1)*(1-1/k) + (1-k/(m+1)))(即元素在列表中的概率乘以它仍然存在的概率)。使用微积分，您可以直接表明它等于k/(m+1)。

你为什么不能做这样的事情

1
2
3
4
5

List GetKRandomFromList(List input, int k)
List ret = new List();
for(i=0;i<k;i++)
ret.Add(input[Math.Rand(0,input.Length)]);
return ret;

我确定您的意思不是那么简单，您可以进一步指定吗？

好吧，您确实至少需要知道N在运行时是什么，即使这涉及对列表进行额外的传递以对其进行计数。最简单的算法是从N中选择一个随机数并删除该项目，重复k次。或者，如果允许返回重复数字，请不要删除该项目。

除非您有一个非常大的N，并且对性能的要求非常严格，否则此算法必须以O(N*k)复杂度运行，应该可以接受。

编辑：没关系，汤姆·霍顿的方法更好。首先选择随机数，然后遍历列表一次。我认为理论上的复杂度相同，但预期的运行时要好得多。