蓄水池抽样算法的问题

蓄水池抽样、或者水库抽样(reservoir sampling)是一种online算法，实现等概率随机抽样。

问题描述

情形 1，你需要从海量样本（总数量未知）中等概率抽取k个数据。

情形 2，当前时刻数据库里没有数据，此后每秒中都会一个新数据进入数据库，k+1秒之后，你需要从数据库中等概率抽取k个数据，并且保证每时每刻这k个数据都是从数据库中等概率抽取的。

一般解决方法

情形 1，先把数据数一遍，得到个数之后，再开始等概率抽取。

情形 2，从第k+1秒开始，每一秒都从整个数据中重新抽取k个。

蓄水池抽样算法

情形 1， 先取出数据库中的前k个数据，然后开始读取下一个数据，我们以k/(k+1)的概率保留这个数据，并且从之前的k个数据中随机挑选一个丢弃，以1/(k+1)的概率不做任务操作。我们继续读取下一个数据，我们以k/(k+2)的概率保留这个数据，并且从之前保留的k个数据中随机挑选一个丢弃，以2/(k+2)的概率不做任何操作。归纳起来，对于第j个数据，我们以k/j的概率保留这个数据，并且从之前保留的k个数据中随机挑选一个丢弃，以(j-k)/j的概率不做任何操作。反复进行，直到遍历完整个数据库。

情形 2， 类似地，一开始我们先保留前k秒产生的数据，此后，第j秒的时候（j > k），我们以k/j的概率保留这个数据，并且从之前保留的k个数据中随机挑选一个丢弃，以(j-k)/j的概率不做任何操作。

相比于一般解决方法，蓄水池的优势显而易见！时间上少了，不用不停地遍历整个数据库来随机抽取，更重要的时候，不用保存历史数据，只需要保存k个已经被选择的数据。省时间、省空间！