水塘抽样算法（Spark RangePartitioner的抽样算法）

        对一个数量未知的样本，希望只经过一次遍历就完成随机抽样，即时间复杂度O(n)。因为样本数量未知，因此就不能通过random函数直接随机抽样。

        希望在n个样本中随机抽取k个数据。即每个数据被抽取的概率为k/n。

        首先我们创建一个k个成员的数组out，用来存放预期抽出的样本。

        （1）当k>=n时，每一个样本被抽取的概率都为100%。因此都可以直接放入数组out。

        （2）当k

        （3）当k

        上一轮抽中的概率 * （不发生抽样的概率 + 发生抽样的概率 * 不被抽走的概率）

        k/(n-1) * ((n-k)/n + k/n * (k-1)/k) = k/n

        概率也为k/n

public class PoolSimple {
    public static void main(String[] args) {
        int[] data = new int[]{1, 3, 4, 5, 2, 12, 53, 54, 2, 4, 325, 46, 7, 2, 2, 423, 563, 23, 24, 6, 1};
        int[] result = new Simple(5).run(data);
        for (int item : result) {
            System.out.println(item);
        }
    }
}

class Simple {

    private final int[] out;
    private final int num;
    private final Random random;

    public Simple(int num) {
        this.num = num;
        this.out = new int[num];
        this.random = new Random();
    }

    
    public int[] run(int[] in) {
        for (int i = 0; i < in.length; i++) {
            if (i < num) {
                out[i] = in[i];
            } else {
                int t1 = random.nextInt(i + 1);
                if (t1 >= num) {
                    int t2 = random.nextInt(num);
                    out[t2] = in[i];
                }
            }
        }
        return out;
    }
}