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

StackOverflow https://stackoverflow.com/questions/54059

题

假设我有一个长度为数字的链表 N. N 非常大，我事先不知道确切的值 N.

我怎样才能最有效地编写一个将返回的函数 k 完全地 随机数 从列表中？

有帮助吗？

解决方案

有一个非常好的且有效的算法，使用称为 水库取样.

让我首先给你它 历史:

高德纳 在 p 上调用此算法 R。他的 1997 年版《半数值算法》（《计算机编程艺术》第 2 卷）第 144 节，并在那里提供了一些代码。Knuth 将这个算法归功于 Alan G。沃特曼。尽管进行了长时间的搜索，我仍然无法找到 Waterman 的原始文档（如果存在），这可能就是为什么您最常看到 Knuth 被引用为该算法的来源。

麦克劳德和贝尔豪斯，1983 (1) 提供了比 Knuth 更彻底的讨论以及该算法有效的第一个发布的证明（据我所知）。

维特 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- 因此看到的结果集是 (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) 概率为我们提供了归纳所需的基本情况。

参考

  1. 麦克劳德，A.伊恩和大卫 R.钟楼。“一种方便的算法，用于绘制简单的随机样品。”皇家统计学会杂志。C系列（应用统计）32.2（1983）：182-184。（关联)

  2. 维特，杰弗里·S.“用储层随机抽样。”数学软件（TOMS）11.1（1985）的ACM交易：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))) （IE。该元素在列表中的概率乘以它仍然存在的概率）。通过微积分，您可以直接证明这等于 k/(m+1).

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

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

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

为什么你不能做类似的事情

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;

我确信你的意思不是那么简单，所以你能进一步说明吗？

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top