题目
题解
问题分析
比如，轮到第1741号球吐出来了，那就要做到从第1号球到第1741号球每一个球进袋子的概率均等。所以，难点在于，它是一个动态的，在动态的每一步，要保证过往的所有球进入袋子的概率均等。
入袋和出袋的机制
首先，在1号球到10号球之间，直接进袋子，没有任何进制；
10号球以后，比如，现在吐出的是第 i 号球，我们以 10/i 的概率决定这个球要不要进入袋子。也就是说我们可以实现一个函数，这个函数传进来 i 的话，等概率返回 1~ i 之间的一个数字，如何返回的数字是 1~10 ，那就把这个球放入袋子；如果返回的数字是大于 10 的，那就不放入袋子，也就是被我们永远扔掉了！
那现在问题来了，如果决定 i 号球进入袋子，但是袋子里只能装下 10 个球，该扔掉哪一个呢？所以，袋子里放的每一个球，不管它是几号球，等概率随机扔掉一个，让 i 号球进来，整个进制就结束了
解释
那么为什么在这个机制下就可以保证吐出的所有球进袋子的概率均等呢？
我们先来想这样一件事情，当前吐出了1729号球（1730号球还没吐），那么3号球在1729号球决定完了之后还在袋子里的概率是多少？如果3号球在1729号球决定完了之后还在袋子里，我们看看3号球经历了什么...
那么，首先1到10号球，3号球在袋子里的机率是百分之百的，就是1。
然后，假设当前来到了第11号球，那么3号球肯定还在袋子里，11号球进入袋子的概率为 10/11，并且3号球出袋的概率为 1/10，所以，11号球到来的时候，3号球出袋子的概率为 10/11 * 1/10，那就是 1/11；那么3号球仍在袋子里的概率就是 10/11了。
现在轮到12号球了，12号球进入袋子的概率为 10/12，3号球出袋的概率为 1/10；那么，12号球到来的时候，3号球出袋子的概率为 1/12；3号球仍在袋子里的概率就是 11/12。
轮到13号球了，13号球以 10/13 的概率进袋子；3号球以 1/10 的概率出袋子；那么13号球到来的时候，3号球出袋的概率为 1/13，仍在袋子里的概率为 12/13。
所以，应该发现规律了...
所以，到第1729号球的时候，3号球仍然在袋子里的概率为 10/1729。
实验
以下实验根据上述例子展开
package com.harrison.class19;
/**
* @author Harrison
* @create 2022-08-05-17:34
* @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。
*/
public class Code02_ReservoirSamplingTest {
// 等概率返回 1 ~ i 中的一个数字
public static int random(int i){
return (int)(Math.random()*i)+1;
}
public static void main(String[] args) {
int test=1000000;
int[] count=new int[1730];
for(int i=0; i<test; i++){
int[] bag=new int[10];
int bagi=0;
for(int num=1; num<=1729; num++){
if(num<=10){
bag[bagi++]=num;
}else{// num>10
if(random(num)<=10){// 一定要把num球放入袋子，否则永远扔掉num球
bagi=(int)(Math.random()*10);
bag[bagi]=num;
}
}
}
for(int num:bag){// 袋子里的每一个球，命中了就把词频加加
count[num]++;
}
}
for(int i=0; i<=1729; i++){
System.out.println(count[i]);
}
}
}没有第0号球，所以第0号球不会选中进入袋子，1729个球，展示不了，只截图了一部分...
因为球的个数太多，实验次数也不是很多，如果把球的个数变少的话，就更能感觉每个球进入袋子的机率几乎是一样的
下图是只有17个球，实验次数为一百万的情况下做的实验，是不是1到17号球每个球进入袋子的概率相等呢？
工程上的应用举例
假设你经营一个非常火的国际游戏，并打算做一个抽奖；你有各个国家的服务器，各地区的服务器，每个人登录可能是某一个地区服务器提供的服务；那么，你需要做到：所有在今天登陆过的用户抽奖一次，比如说1月1号，0点0分抽奖，1月2日0点0分开奖；只要任何一个用户在这个时间段内登录游戏都可以中奖，而且是等概率的，中将用户有100名。怎么设计这
样一个抽奖系统？
如果不用蓄水池问题，得把所有服务器登录的所有名单拿到手，抽100个人，这是一个非常浩大的过程，得上线一个服
务，每一台服务器都得部署这个服务，收集到的用户名单汇报到哪儿，而且还是个比较复杂的一个类似于一个汇总的一个服务；还不知道会不会出错，而且关键在于，可能没有办法在1月2日直接公布得奖名单。为啥，可能1月1日晚上23点以后用户登录还得收集，还得做这样数据整合。所以可能开奖的时候没办法正正好好赶在1月2日的00:00。
如果我们有蓄水池问题，这个问题就变简单了，全球所有的服务器只跟一台服务器沟通，你只用上线一些东西：
1、第几次登录：某一个用户在登陆的时候，他是不是第一次登录；如果时第二次第三次或以后几次登录就不让他参与抽奖；只有在第一次登录时才让它参与抽奖，第几次登录这个常见功能很容易实现。
2、全球第几个登录：接下来，让这个用户知道自己是全球第几号用户登录的。假设是第 i 号登录的，那就以 100/i 的概率决定这个用户进不进奖池；如果以 100/i 的概率决定不进奖池了，那他再也中不了奖了；如果以 100/i 的概率决定进入奖池，那就在奖池中的100个用户随机踢掉一个。
然后，到1月2日00:00的时候，直接公布奖池100个名单，绝对全球所有用户等概率获奖，而且代码的部署轻得多。
代码
package com.harrison.class19;
import org.w3c.dom.ranges.Range;
/**
* @author Harrison
* @create 2022-03-31-8:29
* @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。
*/
public class Code01_ReservoirSampling {
public static class RandomBox{
private int[] bag;
private int N;
private int count;
public RandomBox(int capacity){
bag=new int[capacity];
N=capacity;
count=0;
}
private int rand(int max){
return (int)(Math.random()*max)+1;
}
public void add(int num){
count++;
if(count<=N){
bag[count-1]=num;
}else{
if(rand(count)<=N){
bag[rand(N)-1]=num;
}
}
}
public int[] choices(){
int[] ans=new int[N];
for(int i=0; i<N; i++){
ans[i]=bag[i];
}
return ans;
}
public static void main(String[] args) {
System.out.println("hello");
int all = 100;
int choose = 10;
int testTimes = 50000;
int[] counts = new int[all + 1];
for (int i = 0; i < testTimes; i++) {
RandomBox box = new RandomBox(choose);
for (int num = 1; num <= all; num++) {
box.add(num);
}
int[] ans = box.choices();
for (int j = 0; j < ans.length; j++) {
counts[ans[j]]++;
}
}
for (int i = 0; i < counts.length; i++) {
System.out.println(i + " times : " + counts[i]);
}
}
}
}
