蓄水池抽样算法
给定一个数据流，数据流长度N很大，且N直到处理完所有数据之前都不可知，请问如何在只遍历一遍数据（O(N)）的情况下，能够随机选取出m个不重复的数据。
这个场景强调了3件事：
- 数据流长度N很大且不可知，所以不能一次性存入内存。
- 时间复杂度为O(N)。
- 随机选取m个数，每个数被选中的概率为m/N。
面试中被问到的概率题，才想起学习一下，这篇博客总体参考大佬的博客，但是在证明那里加入了自己的理解。
算法思路：
- 如果接收的数据量小于m，则依次放入蓄水池。
- 当接收到第i个数据时，i >= m，在[0, i]范围内取以随机数d，若d的落在[0, m-1]范围内，则用接收到的第i个数据去替换蓄水池中的第d个数据。
- 重复步骤2。
算法的精妙之处在于：当处理完所有的数据时，蓄水池中的每个数据都是以m/N的概率获得的。
算法证明：
第i个接收到的数据最后能够留在蓄水池中的概率 = 第i个数据进入过蓄水池的概率 * 之后的i+1～N操作里第i个数据不被替换的概率（第i+1到第N次处理 数据i都不会被替换）。
1.当i<=m时，数据直接放进蓄水池，所以第i个数据进入过蓄水池的概率=1。
2.当i>m时，在[1,i]内选取随机数d，如果d<=m，则使用第i个数据替换蓄水池中第d个数据，因此第i个数据进入过蓄水池的概率=m/i。
3.当i<=m时，属于0-m的数据 i 先会进入蓄水池，然而程序从接收到第m+1个数据时开始执行替换操作，第m+1次处理会替换池中数据的概率为m/(m+1)，在池中执行替换 替换掉第i个数据的概率为1/m，则第m+1次处理替换掉第i个数据的概率为(m/(m+1))*(1/m)=1/(m+1)，不被替换的概率为1-1/(m+1)=m/(m+1)。依次，第m+2次处理不替换掉第i个数据概率为(m+1)/(m+2)...第N次处理不替换掉第i个数据的概率为(N-1)/N。所以，之后第i个数据不被替换的概率=m/(m+1)*(m+1)/(m+2)*...*(N-1)/N=m/N。
4.当i>m时，程序从接收到第i+1个数据时才开始有可能替换第i个数据。则参考上述第3点，第i+1个数据对蓄水池里的每个数据d进行替换的概率=m/(i+1) *1/m=1/(i+1)，假设i在蓄水池中，i不被i+1替换的概率为1- 1/(i+1)=i/(i+1)，所以之后的N-i个操作里第i个数据不被替换的概率=i/(i+1)*(i+1)/(i+2)*…*(N-1)/N=i/N。
5.结合第1点和第3点可知，当i<=m时，第i个接收到的数据最后留在蓄水池中的概率=1*m/N=m/N。结合第2点和第4点可知，当i>m时，第i个接收到的数据留在蓄水池中的概率=m/i*i/N=m/N。综上可知，每个数据最后被选中留在蓄水池中的概率为m/N。
拓展：分布式蓄水池抽样（Distributed/Parallel Reservoir Sampling）
一块 CPU 的计算能力再强，也总有内存和磁盘 IO 拖他的后腿。因此为提高数据吞吐量，分布式的硬件搭配软件是现在的主流。如果遇到超大的数据量，即使是 O(N) 的时间复杂度，蓄水池抽样程序完成抽样任务也将耗时很久。因此分布式的蓄水池抽样算法应运而生。运作原理如下：
- 假设有 K 台机器，将大数据集分成 K 个数据流，每台机器使用单机版蓄水池抽样处理一个数据流，抽样 m 个数据，并最后记录处理的数据量为 N1, N2, …, Nk, …, NK(假设 m<Nk)。N1+N2+…+NK=N。
- 取 [1, N] 一个随机数 d，若 d<N1，则在第一台机器的蓄水池中等概率不放回地（1/m=(m-1)/m*1/(m-1)）选取一个数据；若 N1<=d<(N1+N2)，则在第二台机器的蓄水池中等概率不放回地选取一个数据；一次类推，重复 m 次，则最终从 N 大数据集中选出 m 个数据。
推导 m/N：
- 从第 k 台机器的蓄水池中选取一个数据放进最终蓄水池的概率为 Nk/N。（先选机器）
- 第 k 台机器中的蓄水池数据被选取的概率为 m/Nk。（由于每个机器使用单机版蓄水池抽样处理）
- 第 k 台机器蓄水池的一个数据被选中的概率为 1/m。（在选择了机器后，相当于在 k 机器中已经选择了 m 个数，从这里面选一个数据出来）
- 重复 m 次选取，则每个数据被选中的概率为 m*(m/Nk*Nk/N*1/m)=m/N。