水塘抽样算法

水塘抽样（Reservoir sampling）是一系列的随机算法，其目的在于从包含N个项目的集合S中选取k个样本，其中N为一很大或未知的数量，尤其适用于不能把所有N个项目都存放到内存的情况

首先考虑简单的情况，假设k = 1

样本中有N个项目，站在上帝视角，我们知道每个数被选取的概率是。当然对于水塘抽样问题来讲，我们提前不知道这个n的具体数值，无法使用rand函数直接获取结果，何况还有很多变种问题。

我们换一种思路。在我们不知道n的大小的情况下。遍历集合S。因为我们并不知N的大小，每次遍历到一个新元素的时候都认为这是最后一个元素。

• 遇到第一个数时，因为当前只有一个元素。并且要取一个元素，所以一定会取到
• 遇到第二个数时，如果我们以 的概率保留他，那么，
• 遇到第三个数时，如果我们以 的概率保留他，那么，
• 遇到第i个数时，如果我们以 的概率保留他，那么，

所以我们可以得出来一个简单的策略，我们遍历到第i的元素的时候，使用 的概率将它保留下来。使用这个策略就可以保证我们遍历一遍集合S，每个元素被选到的概率都是

对于k >1的情况，可以采用类似的方式进行思考。
站在上帝视角，我们知道每个数被选取的概率是

• 对于前k个数 我们直接保留
• 第k+1个数，如果我们以 的概率保留他。。那么前k个元素被保留的概率
• 第k+2个数，如果我们以 的概率保留他。。那么前k+1个元素被保留的概率
• 第i个数，如果我们以 的概率保留他。 。那么前i个元素被保留的概率

所以我们可以制定这样的策略，对于前k个数，我们可以全部保留。对于第i（i > k）个数以的概率保留它，在保留的基础上，以 的概率和之前保留的元素替换， 就可以保证每个元素被选到的概率都是