水库抽样算法
整理自《大数据算法》（王志宏 哈尔滨工业大学）31页
问题描述
给定一个数据流，从这个流中进行均匀采样。
要求在接收到n个数据后，能够等概率地输出其中的k个数据。
已知n远大于k，且现有的内存空间无法容纳所有数据。
算法描述
准备一个长度为k的数组用于保存样本。
将接收到的前k个数据保存在数组中，
然后对于后续的第i个数据（i > k），掷出一个0~(i-1)之间的随机数，
如果随机数小于k/i，则用第i个数据替换数组中的某个数据，替换位置通过掷出一个0~(k-1)之间的随机数来决定。
如果随机数不小于k/i，则舍弃第i个数据。
这样在接收到多于k个数据后，数组中保留的数据即为当前已接收数据的一个均匀抽样。
算法分析
按照常规的做法，保留n个数据然后从中均匀抽取k个样本，每个数据被抽取的概率为
那么当前这个问题的算法也要保证每个数据被留在数组中的概率为k/n。
假设已经获得了前(n-1)个数据的k个均匀抽样，现在再加入第n个数据，则第n个数据应该有k/n的概率被保留到数组。
而数组中原有的数据，被替换掉的概率为
再算上它们之前被选取为样本的概率k/(n-1)，此时每个原有数据被保留下来的概率为
可见对于新数据和原有数据来说，它们被保留为样本的概率都是相同的。
那么前(n-1)个数据的k个均匀抽样要如何获得呢？这里可以令n = k+1，此时n-1=k，k个样本是唯一确定的。
借助上述算法就可以得到k+1个数据的均匀抽样。循环利用上述算法就能进一步得到前k+2、k+3、k+4个数据的均匀抽样，由此可以推广到任意n > k的情景。
算法的有效性得以证明。
版权声明：本文为shaller原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。