Content #
- 将 1~n 条数据，存入待定长为 n 的集合序列，从这个序列里随机抽取 k 条数据，每条被抽取的概率为：k/n。
- 读到第 k 条数据时：
- 定义第 k 条数据选中的概率为：k/n；
- 如果被选中，在原集合序列中的 n 条数据中随机选择一条，替换为第 k 条的新数据；
- 前 k 条数据被选取后，第 k+1 条数据要么被选取替代为前 k 条中的一条，要么不被选取，概率为 k/n。再依此规则遍历所有的数据。
单机版本实现起来可以如下实现，直接调用 Sampling(k)，就可以得到蓄水池中的 k 个数据。
public class ReservoirSampling {
private int[] ALL; // 整体的水池中的数据
private final int N = 100000; // 整体数据规模
private final int K = 1000; // 水池规模
private Random random = new Random();
public void setUp() throws Exception {
ALL = new int[N];
for (int i = 0; i < N; i++) {
ALL[i] = i;
}
}
private int[] Sampling(int K) {
int[] Pool = new int[K];
for (int i = 0; i < K; i++) { // 前面K个印度人直接进入水池
Pool[i] = ALL[i];
}
for (int i = K; i < N; i++) { // K + 1个元素开始进行概率采样
int r = random.nextInt(i + 1); //这就是K/N的概率
if (r < K) {
Pool[r] = ALL[i]; //如果被选中了，那么这个人就被从蓄水池中挤出来，用新人进去
}
}
return Pool;
}
}