【蓄水池问题】太 nice 了！我中奖啦！

本文主要是介绍【蓄水池问题】太 nice 了！我中奖啦！，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

小伙伴们中过奖么？

是不是都是 中奖绝缘体 呢？

今天我们就来聊一聊关于中奖的 概率 问题~

先思考两个问题

如果让你从规模为 N 的数据序列中，随机选取出 k 个不重复的数据，你会怎么做呢？

• 是不是很简单，知道了总数 N ，等概率随机选择 k 个即可，每个数据被选到的概率均为 $k/N$ 。

问题变一下：那如果从始至终都不知道 N 的具体大小呢？也就是说，数据流长度 N 很大，数据会源源不断的到来，且 N 直到处理完所有数据之前都不可知。

如何在这样的情况下，随机选取 k 个数据，保证当前已经到来的前 i 个元素中每一个元素被选中的概率相等，均为 $k/i$ ，当处理完所有数据结束时，概率自然就变为了 $k/N$ 呢？

两者区别一句话总结：能否提前知道 总数据量 N 。

---

这就引出了今天要探讨的问题：蓄水池算法

蓄水池算法

在一个很大，未知总量的数据流中，抽取 k 个样本，并保证每个样本的选取概率都是 相等并随机 的。

算法思路

1. 构建一个可容纳 k 个样本的数组容器。
2. 当数据量不足 k 个时，全部选取放入数组中。
3. 当数据量超过 k 个时（假设是第 i 个元素），以 $k/i$ 的概率选择进入数组中，并以 $1/k$ 的概率随机替换掉数组中的一个样本元素。
4. 无论样本数据 N 何时结束，均能保证所选元素概率均为 $k/N$ 。

即：保证在动态情况下，已经到来的每个样本元素被选中的概率相等

证明

当 $i\le k$ 时，前 m 个元素，每个被选到的概率均为 $k/m$ 。

当 $i＞k$ 时，前 m 个元素，每个被选到的概率也均为 $k/m$ 。

由以上两种情况的证明，我们可以得出结论：

每个元素被选到的概率均等，均为 $k/N$ 。

---

以上我们证明了该方法的正确性：能够在未知数据量的情况下，依然保证在新元素到来时被选中的概率相等。

代码

public static class RandomBox {// 存放被选的元素数组private int[] arr;// 抽取 k 个样本private int k;// 目前到达的样本总数private int m;// 初始化public RandomBox(int capacity) {arr = new int[capacity];        k = capacity;        m = 0;}// 等概率随机 1 ~ max 之间的一个数private int rand(int max) {return (int) (Math.random() * max) + 1;}// 新到一个元素后，进行选择public void add(int num) {// 总量+1m++;// 没超过k时，直接选入if (m <= k) {arr[m - 1] = num;} else {// 以 k/i 的概率选择进入数组if (rand(m) <= k) {// 随机替换掉其中一个元素，概率 1/karr[rand(k) - 1] = num;}}}}

实际意义

这个算法在现实中有什么意义呢？
抽奖

参与活动中大奖：

今天所有参与活动的小伙伴都有几率中奖哦，今晚24：00整开奖~

假设设置了 10 个奖品，但不知道有多少个人会来参与活动，当 24：00 整时，要公布获奖名单。

此时，就可以选择“蓄水池算法”，活动结束后，遍历一遍结果数组 arr[10]，所有在数组中的 10 个人就是最终的获奖者。每个人的中奖几率均为 10/今天参与活动的总人数 ，确保了活动的公平性。

你中过奖么😜
~ 点赞 ~ 关注 ~ 星标 ~ 不迷路 ~！！！

关注
回复「ACM紫书」获取 ACM 算法书籍 ~
回复「算法导论」获取 算法导论第3版 ~

点赞、转发
让你的小伙伴们一起来学算法吧！！

这篇关于【蓄水池问题】太 nice 了！我中奖啦！的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---