随机取样已死，蓄水池抽样称王

随机取样已死，蓄水池抽样称王

作者简介：大家好，我是爱敲代码的小黄，独角兽企业的Java开发工程师，Java领域新星创作者。个人公众号：爱敲代码的小黄系列专栏：Java设计模式、数据结构和算法如果文章知识点有错误的地方，请指正！和大家一起学习，一起进步如果感觉博主的文章还不错的话，请三连支持一下博主哦博主正在努力完成2022计划中：以梦为马，扬帆起航，2022追梦人

文章目录

一、引言二、蓄水池抽样算法

1. 思路2. 证明3. 代码 三、例题练习四、总结

一、引言

最近小黄的朋友去一家业内有名的游戏公司（有兴趣的读者可以猜猜）面试，出了一道经典的题目：目前游戏需进行一项签到抽奖的活动，怎么保证每个人抽到奖品的概率都是相等的，保证最终中奖的人数为10人

小黄的朋友计算出 签到的总人数，使用随机函数 Random 获取 中奖的人，依次类推，最终求出 10个中奖的人

但面试官并不满意该做法，提出了几个条件：

签到的人数 N 很大且不可知随机选取 10 个人，每个人被选中的概率为 10/N时间复杂度为 O(N)

小黄朋友瞬间有点懵了，不知所措，聊了聊其他的，潦草的结束了这场面试

朋友找小黄聊了聊，最终发现面试官想考察的是：蓄水池抽样算法（Reservoir Sampling）

有精力的读者可以事先看一下这几道 模板 题：

382.链表随机节点398.随机数索引519.随机翻转矩阵497.非重叠矩形中的随机点 二、蓄水池抽样算法

由人数 N 不可知、每个人选中的概率为 10/N、时间复杂度为 O(N) 这几个条件我们可以得知：我们的算法肯定是遍历一次，每个人选中的概率随着签到人数的增加，逐渐变小，但每个人选中的概率一样

比如 num 代表我们逐渐增长的人数：for(int num = 1; num <= 100; num++)

当 num = 10 时，我们每个人数选取的概率为 10/10当 num = 50 时，我们每个人数选取的概率为 10/50当 num = 100 时，我们每个人数选取的概率为 10/100

我们可以看到，随着人数动态的增加，我们的概率也变的不同，如果我们单纯的使用上面 Random 的算法，对于动态的调整我们没有办法

下面，我们一起来领略一下 蓄水池抽样算法 的奥妙所在

1. 思路

我们总体的水池如下：

当前的 num <= 10 时，我们直接让其入水池

当前的 num > 10 时我们在 1~num 进行随机

如果随机的结果小于等于10，则替换该水池如果随机的结果大于10，则不做 *** 作

假设当前的值为 12，我们使用 random.nextInt(12) + 1 得到 1~12 的随机值

假如随机值为 5，则 12 将替换池中下标为 5 的数
假如随机值为 11，则不做 *** 作

最终蓄水池中的数字即为签到中奖的人数

到这一步，我相信 80% 的人会懵，没关系，我也是这样过来的

让我们一起来下面的证明

2. 证明

我们假设当前的 num 为 30，那么每一个值被选中的概率为 10/30

首先，我们证明 3 的概率：

对于 3 来说，入水池概率： 100%100，出水池的概率 = 被替换的概率（也就是 num > 10）

11 能够替换 3 的概率：(10 / 11) * (1 / 10) = (1 / 11)（替换水池的概率 * 随机水池为 3 的概率）12 能够替换 3 的概率：(10 / 12) * (1 / 10) = (1 / 12)… 我们反过来想一下，那么我们 3 不出水池的概率为多少呢？

(3)进水池的概率 * (3)不出水池的概率1 * (10 / 11) * (11 / 12) * (12 / 13) * ... (29 / 30) = (10 / 30)符合我们最后的结果

最后，我们证明 17 的概率：

对于 17 来说，入水池概率：10 / 17，出水池的概率 = 被替换的概率（也就是 num > 17）

18 能够替换 17 的概率：(10 / 18) * (1 / 10) = (1 / 18)（替换水池的概率 * 随机水池为 17 的概率）19 能够替换 17 的概率：(10 / 19) * (1 / 10) = (1 / 19)… 我们反过来想一想，那么我们 17 不出水池的概率为多少呢？

(17)进水池的概率 * (17)不出水池的概率(10 / 17) * (17 / 18) * (18 / 19) * (19 / 20) * ... (29 / 30) = (10 / 30)符合我们最后的结果 3. 代码

public class _蓄水池算法 {
    static Random random = new Random();
    public static void main(String[] args) {
    	// 10000组测试
        int test = 10000;
        // 人数为100人
        int database = 100;
        // 记录每次出现的频率
        int[] count = new int[101];
        for (int i = 0; i < test; i++) {
        	// 蓄水池
            int[] bag = new int[10];
            // 蓄水池下标
            int bagIndex = 0;
            for (int num = 1; num <= database; num++) {
                // 如果小于10,直接入池
                if (num <= 10) {
                    bag[bagIndex++] = num;
                } else {
                    // 如果大于10,则以 10 / i 的概率观察是否可以入池
                    // 如果小于等于10,则证明可以入池
                    if (getNum(num) <= 10) {
                        // 随机淘汰池里面的一个数
                        int index = random.nextInt(10);
                        bag[index] = num;
                    }
                }
            }
            // 记录当前出现的频率
            for (int num : bag) {
                count[num]++;
            }
        }
		// 输出、验证我们的随机率
        for (int i = 0; i < count.length; i++) {
            System.out.println(count[i]);
        }
    }

	// 返回[1,i]的数
    public static int getNum(int i) {
        return random.nextInt(i) + 1;
    }
}

测试结果：我们发现出现的频率基本相等

999
1009
967
1050
981
996
996
950
971
998
1005
1032
974
982
1007
1029
1026
1045

三、例题练习

俗话说的好，一看就会，一做就废，验证你成果的时候到了

力扣模板题目：

382.链表随机节点398.随机数索引519.随机翻转矩阵497.非重叠矩形中的随机点

基本就是模板题，直接套上面的公式即可

容我在这里打一个小小的广告，关注公众号：爱敲代码的小黄，回复：算法源码，不仅可获得蓄水池还有其他各种类型的算法源码。

你的关注可能使我距离成功的顶峰更近一步，一起努力学习，努力成长。

四、总结

基本蓄水池抽样算法到这里就结束了

在工程上主要应用于 抽奖系统，这里可能有人会疑问，我直接等抽奖完毕，然后计算总人数，不也能达到一样的效果嘛。从效果来看，没什么区别性。

但是，工程和理想最大的区别就是：工程可能由于一系列的外在因素影响正常流程的运行。

比如，原本我计划在 2022.1.8~2022.1.10 进行为期2天的抽奖，开奖时间设置在 2022.1.11，如果服务器宕机，导致数据丢失，怎么保证最终的总人数。而我们的 蓄水池抽样算法 则是会一直更新中奖的人数。

当你遇到这类面试题时，直接三步走：原理 -> 证明 -> 代码，一波带走面试官

这期的蓄水池算法到这里就结束了，下一期一定会讲述计算机网络相关知识，提前透漏一下，计算机网络的八股题主也颇有研究。

我是一名独角兽企业的Java开发工程师，希望可以点个关注呀，有问题可以留言或者私信加我微信，我们下期再见！