水塘抽样

背景

在 n 个数中，如何让抽到每一个数的概率相等

可以产生一个随机数，n 个数则在 [1,n] 中产生一个随机数即可

但如果涉及到外部数据，即一次并不能全部读取 n 个数（n 未知）；例如一共 1000 个数据，一次只能加载 10 个，那么再每 10 个加载一次，总共加载 100 次的过程中如何保证最终取到的值满足 1/n

使用水塘抽样算法可以解决

在这里，还分为 K = 1（只抽一个）和 K > 1（抽取多个）

K = 1

分片读取，第 i 个数的概率应该是 1/ i

论证公式

代码

public static int poolSampling(final List<List<Integer>> listList) {
        final Random random = new Random();

    	// 记录当前是第一个数字，即 i ，使用这个值使选中当前值的几率为 1/i
        int count = 0;
    	// 返回值，随机的数字 i
        int res = 0;
    	// 假设 listList 是一个需要分次读取的文件
        for (final List<Integer> list : listList) {
            // 每一次读取
            for (final Integer i : list) {
                count++;
                // 从 [0,n] 中随机一个数，如果是 0，则替换 res
                // 即 1/i 的几率被选中了
                if (random.nextInt(count) == 0) {
                    res = i;
                }
            }
        }
        return res;
    }

K > 1

和 K = 1 思路一致，区别在于 1/i 的概率升级为 k/i

论证公式

代码

public static int[] poolSampling(final List<List<Integer>> listList, final int k) {
    final Random random = new Random();

    int count = 0;
    // 多个返回值
    final int[] res = new int[k];
    for (final List<Integer> list : listList) {
        for (final Integer i : list) {
            count++;
            // 因为 i/k 的几率，所以让 resIndex < k，则 resIndex 一定落在返回值数组中
            final int resIndex = random.nextInt(count);
            // 满足 i/l 几率（从 0 开始，则小于即可）
            if (resIndex < k) {
                // 记录
                res[resIndex] = i;
            }
        }
    }
    return res;
}

s

参考

随机算法：水塘抽样算法 - 知乎 (zhihu.com)

398. 随机数索引 - 力扣（LeetCode） (leetcode-cn.com)

382. 链表随机节点 - 力扣（LeetCode） (leetcode-cn.com)