Reservoir Sampling

解决的问题

要求从N个元素中随机的抽取k个元素，其中N无法确定。
这种应用的场景一般是数据流的情况下，由于数据只能被读取一次，而且数据量很大，并不能全部保存，因此数据量N是无法在抽样开始时确定的；但又要保持随机性

证明过程

假设数据序列的规模为 nn，需要采样的数量的为 kk。

首先构建一个可容纳 kk 个元素的数组，将序列的前 kk 个元素放入数组中。

然后从第 k+1 个元素开始，以 $\frac {k}{n}$ 的概率来决定该元素是否被替换到数组中（数组中的元素被替换的概率是相同的）。 当遍历完所有元素之后，数组中剩下的元素即为所需采取的样本。

对于第 i个数（i≤k）。在 k 步之前，被选中的概率为 1。当走到第 k+1 步时，被 k+1 个元素替换的概率 = k+1个元素被选中的概率 * i 被选中替换的概率，即为 $\frac{k}{k+1}×\frac{1}{k}=\frac{1}{k+1}$。则被保留的概率为 $1−\frac{1}{k+1}=\frac{k}{k+1}$。依次类推，不被 k+2个元素替换的概率为 $1−\frac{k}{k+2}×\frac{1}{k}=\frac{k+1}{k+2}$。则运行到第 n步时，被保留的概率 = 被选中的概率 * 不被替换的概率，即：

$$1×\frac{k}{k+1}×\frac{k+1}{k+2}×\frac{k+2}{k+3}×…×\frac{n−1}{n}=\frac{k}{n}$$

对于第 j 个数（j>k）。在第 j 步被选中的概率为 kjkj。不被 j+1j+1 个元素替换的概率为 1−kj+1×1k=jj+11−kj+1×1k=jj+1。则运行到第 nn 步时，被保留的概率 = 被选中的概率 * 不被替换的概率，即：

$$\frac{k}{j}×\frac{j}{j+1}×\frac{j+1}{j+2}×\frac{j+2}{j+3}×…×\frac{n−1}{n}=\frac{k}{n}$$

所以对于其中每个元素，被保留的概率都为 $\frac{k}{n}$.

public class ReservoirSamplingTest {

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

    @Before
    public void setUp() throws Exception {
        // 初始化
        pool = new int[N];
        for (int i = 0; i < N; i++) {
            pool[i] = i;
        }
    }

    private 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);
            if (r < K) {
                result[r] = pool[i];
            }
        }

        return result;
    }

    @Test
    public void test() throws Exception {
        for (int i : sampling(100)) {
            System.out.println(i);
        }
    }
}

• 注意random部分
• 以及r<K

保证$\frac{k}{n}$的概率