蓄水池抽样

** 问题：** 给出一个数据流，这个数据流的长度很大或者未知。并且对该数据流中数据只能访问一次。请写出一个随机选择算法，使得数据流中所有数据被选中的概率相等。

思路： 解决方案就是蓄水池抽样（reservoir sampling）。主要思想就是保持一个集合作为蓄水池，依次遍历所有数据的时候以一定概率替换这个蓄水池中的数字。

对这个问题首先从最简单的情况出发：

  1. 数据流只有一个数据。直接返回该数据，该数据返回的概率为1。

  2. 假设数据流里有两个数据。 读到了第一个数据，这次不能直接返回该数据，因为数据流没有结束。继续读取第二个数据，发现数据流结束了。因此只要保证以相同的概率返回第一个或者第二个数据就可以满足题目要求。因此我们生成一个0到1的随机数R,如果R小于0.5就返回第一个数据，如果R大于0.5，返回第二个数据。

  3. 接着分析有三个数据的数据流的情况。假设流中的数据命名为1、2、3。我们陆续收到了数据1、2和前面的例子一样，只能保存一个数据，所以必须淘汰1和2中的一个。首先按照二分之一的概率淘汰一个，例如淘汰了2。继续读取流中的数据3，发现数据流结束了，我们知道在长度为3的数据流中，如果返回数据3的概率为1/3,那么才有可能保证选择的正确性。也就是说，目前我们手里有1,3两个数据，我们通过一次随机选择，以1/3的概率留下数据3，以2/3的概率留下数据1，那么数据1被最终留下的概率是：

    数据1被留下：（1/2）*(2/3) = 1/3

    数据2被留下概率：（1/2）*(2/3) = 1/3

    数据3被留下概率：1/3

因此结论如下：假设当前正要读取第n个数据，则以1/n的概率留下该数据，否则留下前n-1个数据中的一个。以这种方法选择，所有数据流中数据被选择的概率一样。证明如下：

假设n-1时候成立，即前n-1个数据被返回的概率都是1/n-1。
当前正在读取第n个数据，以1/n的概率返回它。那么前n-1个数据中数据被返回的概率为返回n-1个数据中的一个且第n个数据不被选中，即：(1/(n-1))*((n-1)/n)= 1/n，假设成立。

问题扩展：给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）。
这次与上面唯一的不同是：总共需要取k个元素。

方案：以1的概率取前k个元素放到蓄水池中，从i=k+1开始，以k/i的概率取第i个元素，若被取，以均等的概率替换先前被取的k个元素。

证明：当i=k+1时：第k+1个元素以k/k+1概率被取，前k个元素被取的概率=1 - 被第k+1个元素替换的概率=1-k/(k+1)*1/k=k/(k+1) 符合条件。

设i=p时符合条件，即前p个元素都以k/p的概率被取。

则i=p+1时：对第p+1个元素，被取概率为k/(p+1)符合条件。 对于前p个元素，每个元素被取的概率=被取并且没有被第p+1个元素替换的概率= k/p*((1-k/(p+1))+k/(p+1)*(1-1/k))=k/p+1同样符合条件。

综上所述：得证。

分布式蓄水池抽样

要进行容量为k的分布式蓄水池抽样，使用mapreduce 模拟sql中的ORDER BY RAND (随机抽取)。对于集合中的每一个元素，都产生一个0-1的随机数，之后选取随机值最大的前k个元素。这种方法在对大数据集进行分层抽样的时候非常管用。这里每一个分层都都是一些分类变量如性别，年龄，地理信息等的组合。注意如果输入的数据集分布极端的不均匀，那么抽样可能不能覆盖到所有的层级。

加权分布式蓄水池抽样

问题：集合中的数据是有权重的，算法希望数据被抽样选中的概率和该数据的权重成比例。

思路：对于每个数据计算一个0-1的值R，并求r的n次方根作为该数据的新的R值。这里的n就是该数据的权重。最终算法返回前k个R值最高的数据然后返回。根据计算规则，权重越大的数据计算所得的R值越接近1，所以越有可能被返回。