40

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

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

4

6 回答 6

42

有一个非常好的和有效的算法，使用一种叫做储层采样的方法。

让我从给你它的历史开始：

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 结果集中的元素在-seen 结果集中被替换的概率n+1为(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结果集包括具有 (=1) 概率的每个元素，s/n为我们提供了必要的归纳基础案例。

参考

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

  2. Vitter, Jeffrey S. “水库随机抽样”。ACM 数学软件交易 (TOMS) 11.1 (1985): 37-57。（链接）

于 2014-01-18T07:31:39.577 回答
34

这称为储层采样问题。简单的解决方案是为列表的每个元素分配一个随机数，如您所见，然后保持顶部（或底部）k 个元素按随机数排序。

于 2008-09-10T13:54:13.030 回答
2

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

如果您不知何故不知道链表的长度（如何？），那么您可以将第一个 k 抓取到一个数组中，然后对于节点 r，在 [0, r) 中生成一个随机数，如果它小于比 k，替换数组的第 r 项。（不完全相信没有偏见......）

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

于 2008-09-10T13:45:28.900 回答
1

如果您不知道列表的长度，那么您将必须完整地遍历它以确保随机选择。我在这种情况下使用的方法是 Tom Hawtin ( 54070 ) 所描述的方法。在遍历列表时，您将k构成随机选择的元素保留到该点。（最初你只是添加k你遇到的第一个元素。）然后，你用列表中的第 th 个元素（即你当时所在的元素）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)。

于 2008-09-10T14:22:07.487 回答
-3

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

除非你有一个非常大的 N 和非常严格的性能要求，否则这个算法运行起来很O(N*k)复杂，这应该是可以接受的。

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

于 2008-09-10T13:45:55.187 回答
-3

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

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;

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

于 2008-09-10T13:49:25.617 回答