蓄水池抽样算法

问题描述：
给定一个数据流，要求从n个元素中等概率的采样k个样本点，n的数值未知并且数量很大。
解析：
如果n知道并且数据量内存可以接受，则直接加载到内存中处理。现在是未知并且很大。
采用蓄水池的算法，设置一个容量为k的水池，将前k个元素直接加入到蓄水池中，对于从k+1后面的第i个元素，处理过程分为两步：1.首先确定当前元素要不要选择，选中的概率为\(\frac{k}{i}\)，如果选择则从水池中选择一个已有元素被替换掉，最终保证每个元素被选中的概率为\(\frac{k}{n}\).
采用归纳法来证明：
当i=k+1时，第i个元素被选中的概率为\(\frac{k}{k+1}\)，则前面k个元素被当前元素替换掉的概率为\(\frac{k}{k+1}*\frac{1}{k}=\frac{1}{k+1}\)，则前面k个元素被选中的概率为1-被替换的概率=\(1-\frac{1}{k+1}=\frac{k}{k+1}\)。说明前k+1个元素被选中的概率相等且均为\(\frac{k}{k+1}\)。
假设i=n时前面元素被选中的概率均为\(\frac{k}{n}\)
那么当i=n+1时，第n+1个元素被选中的概率为\(\frac{k}{n+1}\)。对于前面的n个元素，每个元素被选中的情况分为两种：1.前面n次已经被选中并且第n+1次时，第n+1个元素没有被选中；2.前面n此已经被选中，第n+1个元素被选中但是没有将其替换掉。
不难写出此时的概率为：
\(\frac{k}{n}*(1-\frac{k}{n+1}) + \frac{k}{n}*\frac{k}{n+1}*(1-\frac{1}{k})=\frac{k}{n+1}\)
由此可见第n+1步也满足假设，问题得证。

参考：
https://www.cnblogs.com/python27/p/Reservoir_Sampling_Algorithm.html
http://blog.csdn.net/bitcarmanlee/article/details/52719202