蓄水池采样算法

在不知道数据规模的情况下进行采样，就要用到蓄水池采样算法。

算法过程

假设数据总规模为N,需要采样k个数。那么先构建一个k大小的数组result，将数据的前k个数放进去。然后从第k+1个数开始，产生一个随机数r，如果这个r < k，则将当前遍历到的数替换result[r]。

这个算法保证了数组中的元素被替换的概率是相同的，都为 k/n。证明如下：(图源https://www.cnblogs.com/snowInPluto/p/5996269.html)

code

import java.util.*;
public class Solution {

    private static int[] pool; // 所有数据
    private static final int N = 100000; // 数据规模
    private static Random random = new Random();

    public static void setUp(){
        // 初始化
        System.out.println("初始化");
        pool = new int[N];
        for (int i = 0; i < N; i++) {
            pool[i] = i;
        }
    }
    private static int[] sampling(int K) {
        int[] result = new int[K];
        for (int i = 0; i < K; i++) { // 前 K 个元素直接放入数组中
            result[i] = pool[i];
        }

        for (int i = K; i < N; i++) { // 从第K + 1 个元素开始进行概率采样
            int r = random.nextInt(i + 1);  //从[0,i]中随机选一个数
            if (r < K) {
                result[r] = pool[i];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        setUp();
        for (int i : sampling(100)) {
            System.out.println(i);
        }
    }
}