从链表中有效地select一组随机元素
说我有一个长度为N的数字的链表。 N很大，我不知道N的确切值。
我怎样才能最有效地写一个函数，将从列表中返回k完全随机数字 ？
有一个非常好的和有效的algorithm，使用称为油藏采样的方法。
让我开始给你它的历史 ：
Knuth将这个algorithmR称为p。 他在1997年版的“mathalgorithm”（“计算机程序devise艺术”第2卷）中的144页，并为其提供了一些代码。 Knuth将algorithm归结为Alan G. Waterman。 尽pipesearch了很长时间，但是如果存在的话，我一直无法find沃特曼的原始文档，这也许就是为什么你经常看到克努特引用这个algorithm的来源。
McLeod和Bellhouse，1983 （1）比Knuth提供了一个更彻底的讨论，以及第一个发现的证据（我知道）algorithm的工作原理。
Vitter 1985 （2）评论algorithmR，然后提出了另外三个algorithm提供相同的输出，但扭曲。 他的algorithm不是select包含或跳过每个入局元素，而是预先确定要跳过的入局元素的数量。 在他的testing中（无可否认，这个testing已经过时了）通过避免随机数字的产生和每个input数字的比较，大大缩短了执行时间。
在伪代码中，该algorithm是：
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()
请注意，我已经专门编写了代码，以避免指定input的大小。 这是这个algorithm的一个很酷的属性：你可以运行它，而不需要事先知道input的大小，它仍然保证你遇到的每个元素有相等的概率结束在R （也就是说，没有偏压）。 此外， R包含algorithm一直考虑的元素的公平和代表性样本。 这意味着你可以使用这个在线algorithm 。
为什么这个工作？
McLeod和Bellhouse（1983）提供了一个使用组合math的certificate。 这很漂亮，但在这里重build会有点困难。 因此，我已经生成了一个更容易解释的替代certificate。
我们通过归纳certificate进行。
假设我们想要生成一组元素，而且我们已经看到了n>s元素。
假设我们当前s元素已经以概率s/n被select了。
根据algorithm的定义，我们select元素n+1 ，概率为s/(n+1) 。
每个元素已经是我们结果集的一部分，被replace的概率为1/s 。
(1/s)*s/(n+1)=1/(n+1)因此n+1结果集中的元素被置换的概率是可以被置换的。 相反，元素不被replace的概率是1-1/(n+1)=n/(n+1) 。
因此， n+1结果集包含一个元素，如果它是n seen结果集的一部分并且没有被replace – 这个概率是(s/n)*n/(n+1)=s/(n+1) —或者如果元素被select—概率为s/(n+1) 。
algorithm的定义告诉我们，第一个元素被自动包含为结果集的第一个n=s成员。 因此， n-seen的n-seen结果集包括每个具有s/n （= 1）概率的元素， s/n为我们提供了诱导的必要基本情况。
参考
-
McLeod，A. Ian和David R. Bellhouse。 “绘制简单随机样本的简便algorithm”。 英国皇家统计学会杂志。 系列C（应用统计）32.2（1983）：182-184。 （ 链接 ）
-
Vitter，Jeffrey S.“随机抽取一个储层”。 ACM Transactions on Mathematical Software（TOMS）11.1（1985）：37-57。 （ 链接 ）
这被称为水库采样问题。 简单的解决scheme是随机数赋予列表中的每个元素，然后按照随机数的顺序保留顶部（或底部）k个元素。
我会build议：首先find你的k个随机数字。 sorting他们。 然后遍历链表和你的随机数字一次。
如果你不知道链表的长度（如何？），那么你可以抓住第一个k到一个数组中，然后对于节点r，在[0，r）中生成一个随机数，如果这样比k更换数组的第rth项。 （不完全相信，不偏向…）
除此之外：“如果我是你，我不会从这里出发。” 你确定链表是适合你的问题吗？ 是不是有一个更好的数据结构，比如一个好的旧平面数组列表。
如果你不知道列表的长度，那么你将不得不遍历它完成，以确保随机select。 我在这种情况下使用的方法是Tom Hawtin（ 54070 ）描述的方法。 在遍历列表的时候，你保留了k元素，这些元素组成了你的随机select。 （最初只需要添加所遇到的前k元素。）然后，用概率k/i ，用列表中的第i个元素（即当时的元素）replace您的select中的随机元素。
很容易certificate这是一个随机select。 在看到m元素（ m > k ）之后，我们已经知道列表中的前m元素中的每一个都是你随机select的一部分，概率为k/m 。 这最初举行是微不足道的。 然后，对于每个元素m+1 ，将其放入您的select中（replace一个随机元素），概率为k/(m+1) 。 您现在需要显示所有其他元素也有被选中的概率k/(m+1) 。 我们有这个概率是k/m * (k/(m+1)*(1-1/k) + (1-k/(m+1))) （即元素在列表中的概率乘以它仍然存在的概率）。 用微积分可以直接表明这等于k/(m+1) 。
那么，你至less需要知道N在运行时是怎样的，即使这需要在列表上额外传递一遍。 最简单的algorithm就是在N中选取一个随机数，然后移除该项，重复k次。 或者，如果允许返回重复号码，请勿移除该项目。
除非你有非常大的N和非常严格的性能要求，否则这个algorithm运行的复杂度是O(N*k) ，这应该是可以接受的。
编辑：没关系，汤姆霍金的方法更好。 先select随机数，然后遍历列表一次。 我认为同样的理论复杂性，但更好的预期运行时间。
你为什么不能做点什么
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;
我相信你不是指那么简单的东西，你可以进一步指定吗？
