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

Question

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

algorithmlanguage-agnosticlist

40

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

我该如何编写最有效的函数，以从列表中返回k个完全随机的数？

- Matt Sheppard

6个回答

33

这被称为蓄水池抽样问题。简单的解决方案是在看到列表中的每个元素时，为其分配一个随机数，然后按照随机数的顺序保留前（或后）k个元素。

- Bill the Lizard

有没有想过为什么这个叫做“蓄水池抽样”？ - Lazer

@Lazer：我不确定 Vitter（PDF）最初是不是创造了这个术语，但他将这个问题表述为“从 N 条记录的池子中无重复地选择 n 条记录的随机样本...”（强调我的）。在第2节中，他给出了一个定义，开始时是“The first step of any reservoir algorithm is to put the first n records of the file into a 'reservoir.'...” - Bill the Lizard

这很优雅。但是，我有一个疑问。如果在分配给我们的流中有重复的随机数，怎么办？假设排序后的第k个和第（k+1）个元素被分配了相同的数字，并且仅选择前K个将“取决于”我们如何打破平局..对吗？请您能否澄清一下。 - phanin

@phani 如果你在使用一个范围内的随机整数，那可能会有问题。如果你只是使用一个随机双精度浮点数，重复值对你样本的随机性应该没有什么影响。 - Bill the Lizard

@BilltheLizard 对于任意精度的实数，这是正确的。但是doubles使用几位指数，因此使用普通的64位整数可能会更好。 - dtldarek

2

我建议：首先找到您的 k 个随机数。将它们排序。然后遍历链表和随机数。

如果您不知道链表的长度（如何？），那么您可以将前 k 个节点存入数组中，然后对于节点 r，在 [0，r) 中生成一个随机数，如果小于 k，则替换数组的第 r 个元素。（我不完全相信这不会有偏差...）

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

- Tom Hawtin - tackline

嗨Tom - 抱歉，我不太明白 - 你所说的“首先找到你的k个随机数”是什么意思。目标是从列表中找到k个随机数 - 或者我有什么误解吗。 - Matt Sheppard

@TomHawtin，没有偏见：请看我的答案。 - Richard

2

如果你不知道列表的长度，那么你将需要完全遍历它以确保随机挑选。我在这种情况下使用的方法是由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)。

- mweerden

1

这应该是被选中的答案。 - Luca Fiaschi

-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;

我相信你不是指那么简单的事情，你能再具体地说明吗？

- George Mauer

这种方法低效的原因在于，对于链表来说，在第四行获取input[x]的值非常昂贵，因为你必须遍历所有项直到x才能到达那里 - 而你的解决方案会执行k次。正如其他答案所指出的那样，你可以通过单次遍历列表来完成它。 - Matt Sheppard

-3

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

除非您有一个非常大的N和非常严格的性能要求，否则此算法的复杂度为O（N * k），应该可以接受。

编辑：不用管了，Tom Hawtin的方法更好。先选择随机数，然后遍历列表一次。我认为理论复杂度相同，但期望运行时间更短。

- Gorgapor

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Richard · Accepted Answer

有一个非常好的、高效的算法可以使用一种叫做“蓄水池抽样”的方法来实现。

让我先给你讲一下它的历史：

Knuth在他1997年版的《计算机编程艺术》第二卷《半数值算法》的第144页中将这个算法称为R算法，并在那里提供了一些代码。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+1结果集中，来自n结果集的元素被替换的概率为(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），这为归纳提供了必要的基本情况。

参考资料：

1. McLeod, A. Ian和David R. Bellhouse。“一种方便的抽取简单随机样本的算法。”皇家统计学会杂志。C系列（应用统计）32.2（1983）：182-184。（Link）

2. Vitter，Jeffrey S。“使用水库进行随机抽样。” ACM数学软件交易（TOMS）11.1（1985）：37-57。（Link）