2014-08-24
蓄水池算法（Reservoir algorithm）的几种描述：
现在有一组数，不知道这组数的总量有多少，请描述一种算法能够在这组数据中随机抽取k个数，使得每个数被取出来的概率相等。
------ 分割线 ------
给出一个数据流，这个数据流的长度很大或者未知。并且对该数据流中数据只能访问一次。请写出一个随机选择算法，使得数据流中所有数据被选中的概率相等。
如果蓄水池内只能放一个数据
- 数据流中的第1个数据出现，只有1个数据则放入蓄水池的概率是1，即直接放入蓄水池。
- 数据流中的第2个数据出现，现在已经出现2个数据了，每个数据出现在蓄水池的概率是1/2。我们以1/2的概率将这第2个数据保留（即以1/2的概率将第2个数据放入蓄水池），故对于第1个数据而言，其被保留的可能性是：第1个数据被选中用于被替换的概率*第2个数据未被保留的概率，即
1*(1-1/2) = 1/2。 - 数据流的第3个数据出现，现在已经出现3个数据了，每个数据出现在蓄水池的概率是1/3。我们以1/3的概率保留第3个数据，蓄水池有1/2的概率存储第1个数据，故蓄水池保留第1个数据的可能性是第1个数据被选中用于被替换的概率*第3个数据未被保留的概率，即
1/2*(1 - 1/3) = 1/3。同理，蓄水池保留第2个数据的可能性也是1/3。
按照上面的思路继续下去，若最终数据流中有N个数据，每个数据存放在蓄水池中的可能性必然是1/N。
这里有一个问题是如何以某一概率来保留某个数据。假如概率是1/3，可以这样实现：
# !/usr/bin/env ruby
# coding: UTF-8
num = Random.rand(1..3) # 生成不小于1,不大于3的随机整数
if num <=1
puts '保留该数据'
else
puts '不保留该数据'
end
如果蓄水池内能存放多个数据
假设蓄水池能够存放8个数据，如果数据流的总的数据个数不大于8，那么直接将这8个数据放进蓄水池即可。如果数据流中数据总数大于8,那么先把数据流的前8个数据放进蓄水池吧，因为此时前8个数据每一个是以8/8的概率放入蓄水池。然后：
- 数据流中的第9个数据出现。此时要求从这9个数据中随机拿出8个放入蓄水池，即每个数据以8/9的概率出现在蓄水池中。由于前8个数据已经放入蓄水池中，我们以8/9的概率保留第9个数据（即存放到蓄水池）。若确定第9个数据被保留，则随机的去掉蓄水池中的一个数据，将第9个数据添进去即可。
- 数据流中的第10个数据出现。我们以8/10的概率保留第10个数据。若确定第10个数据被保留，则随机的去掉蓄水池中的一个数据，将第10个数据添进去即可。
具体证明可见蓄水池抽样算法证明。
按照上面的思路继续下去，若最终数据流中有N个数据，每个数据存放在蓄水池中的可能性必然是8/N。
取样问题
无论是从数据流还是从具体的N个元素中随机取出不同的m个元素，都可以使用蓄水池算法。