蓄水池抽样算法

给定一个数据流，数据流长度N很大，且N直到处理完所有数据之前都不可知，请问如何在只遍历一遍数据（O(N)）的情况下，能够随机选取出k个不重复的数据
要求有三点：

• 不能直接取N内的m个随机数，然后按索引取出数据
• 不能先遍历一遍，然后分块存储数据，再随机选取
• 需要保证数据选取绝对随机的保证。

设置蓄水池的大小为k
证明所有元素概率都是k/n
i代表第i个接受到的元素

• i<=k时，蓄水池不满，数据直接放入，所以进入蓄水池的概率是 1
• 当i>k时，在[1,i]内随机选取m，如果m<=k，那么要用第i个替换m,因此第i个数进入蓄水池的概率是k/i
• 当i<=k时，程序从接收到第k+1个数据时开始执行替换操作，第k+1次处理会替换池中数据的为k/(k+1)，会替换掉第i个数据的概率为1/k，则第k+1次处理替换掉第i个数据的概率为(k/(k+1))(1/k)=1/(k+1)，不被替换的概率为1-1/(k+1)=k/(k+1)。依次，第k+2次处理不替换掉第i个数据概率为(k+1)/(k+2)...第N次处理不替换掉第i个数据的概率为(N-1)/N。所以，之后第i个数据不被替换的概率=k/(k+1)(k+1)/(k+2)...(N-1)/N=k/N
• 每个数据最后被选中留在蓄水池中的概率为k/N

import random
class resiver():
    def __init__(self,size):
        self.sample=[]
        self.size=size
        self.counter=0
    def pick(self,item):
        self.counter+=1
        if len(self.sample)<self.size:
            self.sample.append(item)
        randex=random.randint(1,self.counter)
        if randex<self.size:
            self.sample[randex-1]=item
        return self.sample