蓄水池抽样

参考

问题描述

给出一个数据流，我们需要在此数据流中随机选取 k 个数。由于这个数据流的长度很大，因此需要边遍历边处理，而不能将其一次性全部加载到内存。

请写出一个随机选择算法，使得数据流中所有数据被等概率选中。

这种问题的表达形式有很多。比如让你随机从一个矩形中抽取 k 个点，随机从一个单词列表中抽取 k 个单词等等，要求你等概率随机抽取。不管描述怎么变，其本质上都是一样的。今天我们就来看看如何做这种题。

算法描述

这个算法叫蓄水池抽样算法（reservoid sampling）。

其基本思路是：

• 构建一个大小为 k 的数组，将数据流的前 k 个元素放入数组中。
• 对数据流的前 k 个数先不进行任何处理。
• 从数据流的第 k + 1 个数开始，在 [1, i] 之间选一个数 rand，其中 i 表示当前是第几个数。
• 如果 rand 大于等于 k 什么都不做
• 如果 rand 小于 k， 将 rand 和 i 交换，也就是说选择当前的数代替已经被选中的数（备胎）。
• 最终返回幸存的备胎即可

这种算法的核心在于先以某一种概率选取数，并在后续过程以另一种概率换掉之前已经被选中的数。因此实际上每个数被最终选中的概率都是被选中的概率 * 不被替换的概率。

Init : a reservoir with the size： k
for i= k+1 to N
    if(random(1, i) < k) {
        SWAP the Mth value and ith value
    }

每个要求是k/n, 对于前k个，概率为1*（1-1/(k+1)) * (1-1/(k+2)) *(1-1/n)… = k/n

对于第i(i>k)个，