用百度云服务器做网站,微信视频号怎么引流推广,网站建设网站模版,开发公司与建筑公司合作协议蓄水池抽样#xff0c;也称水塘抽样#xff0c;是随机抽样算法的一种。基本抽样问题有一批数据#xff08;假设为一个数组#xff0c;可以逐个读取#xff09;#xff0c;要从中随机抽取一个数字#xff0c;求抽得的数字下标。常规的抽样方法是#xff0c;先读取所有的…蓄水池抽样也称水塘抽样是随机抽样算法的一种。基本抽样问题有一批数据假设为一个数组可以逐个读取要从中随机抽取一个数字求抽得的数字下标。常规的抽样方法是先读取所有的数字记录数字的总个数记为n。然后产生一个0 ~ n - 1范围内的随机数即可即随机抽取的数字下标index为其中rand为随机数产生函数。但是上述常规抽样方法有一个局限性就是必须读取完所有的数字之后才可以计算下标。一方面如果数据量很大一次性读入所有的数据需要很大的内存。另外一方面很多流式数据往往都是不断在读取数据如果要读完所有的数据还需要额外记录度过的数据。那么能不能边读数据边计算并且度过的数据不要记录了呢蓄水池抽样基本算法这里就要用到今天要讲的蓄水池抽样算法用index记录最终得到随机数下标该算法简述如下从前往后不断读取数字读到第i从0开始个数字时在[0, i]范围内产生一个随机数r如果r 0那么index i,否则index维持原来的的值那么最终index就是产生的随机数的下标。下面来证明这个算法的正确性证明算法的正确性即使要证明每个数字抽到的概率相等。假设数字的中个数为n那么这些数字的下标为0 ~ n - 1设抽到下标为i的数字的概率为P(i)根据上面的描述要抽到下标为i的数字要满足的条件为在读到第i个数字时[0, i]范围内产生的随机数为0这样index i在读到第i个数字之后的数字时不能再产生随机数0否则index就为k了从上面的计算可以看到每个数字抽到的概率为1/n因此该抽样的方法是正确的。很多人有一点疑惑通过上面的方法一定会抽到某个数字吗答案是肯定的因为在读到第0个数字时从[0,0]中产生一个随机数肯定是0。因此下标为0的梳子一开始肯定会被选中如果后续没有其它数字选中的话就是下标为0的数字了从而保证一定有一个数字被选中。蓄水池抽样算法的变式假如并不是从所有的数字中抽取而是从满足某些条件的数字中抽取。假如这些数字中有多个数字x要从所有的数字x中抽出一个数字求最后抽得的数字x的下标。只需要将上面方法中的i换成x的计数就好从前往后不断读取数字读到第k个数字时若该数字为x设为第i个x在[0, i]范围内产生一个随机数r如果r 0那么index k,否则index维持原来的的值那么最终index就是产生的随机数的下标。
