蓄水池算法

简介: 蓄水池算法

题目

在这里插入图片描述

题解

问题分析

比如,轮到第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]);
            }

        }
    }
}
相关文章
|
1月前
|
机器学习/深度学习 算法 大数据
蓄水池抽样算法详解及Python实现
蓄水池抽样是一种适用于从未知大小或大数据集中高效随机抽样的算法,确保每个元素被选中的概率相同。本文介绍其基本概念、工作原理,并提供Python代码示例,演示如何实现该算法。
34 1
|
算法 数据处理
海量数据处理之蓄水池抽样算法
一、问题由来       这个题目的由来是在《编程珠玑》里遇到的,故记录一下。还可以这么说,”如何从二进制文件中等概率取整数?”或者”在不知道文件总行数的情况下,如何从文件中随机的抽取一行?”这个题目说的有点不清楚实际上是:一个二进制文件中有好多好多整数,你要随机取出一个。
1831 0
|
算法 Java C++
Reservoir Sampling 蓄水池抽样算法,经典抽样
随机读取数据,如何保证真随机是不可能的,因为计算机的随机函数是伪随机的。 但是在不考虑计算机随机函数的情况下,如何保证数据的随机采样呢? 1.系统提供的shuffle函数   C++/Java都提供有shuffle函数,可以对容器内部的数据打乱,保持随机排序。
1433 0
|
18小时前
|
机器学习/深度学习 算法
基于改进遗传优化的BP神经网络金融序列预测算法matlab仿真
本项目基于改进遗传优化的BP神经网络进行金融序列预测,使用MATLAB2022A实现。通过对比BP神经网络、遗传优化BP神经网络及改进遗传优化BP神经网络,展示了三者的误差和预测曲线差异。核心程序结合遗传算法(GA)与BP神经网络,利用GA优化BP网络的初始权重和阈值,提高预测精度。GA通过选择、交叉、变异操作迭代优化,防止局部收敛,增强模型对金融市场复杂性和不确定性的适应能力。
100 80
|
19天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。
|
25天前
|
机器学习/深度学习 算法 Serverless
基于WOA-SVM的乳腺癌数据分类识别算法matlab仿真,对比BP神经网络和SVM
本项目利用鲸鱼优化算法(WOA)优化支持向量机(SVM)参数,针对乳腺癌早期诊断问题,通过MATLAB 2022a实现。核心代码包括参数初始化、目标函数计算、位置更新等步骤,并附有详细中文注释及操作视频。实验结果显示,WOA-SVM在提高分类精度和泛化能力方面表现出色,为乳腺癌的早期诊断提供了有效的技术支持。
|
5天前
|
供应链 算法 调度
排队算法的matlab仿真,带GUI界面
该程序使用MATLAB 2022A版本实现排队算法的仿真,并带有GUI界面。程序支持单队列单服务台、单队列多服务台和多队列多服务台三种排队方式。核心函数`func_mms2`通过模拟到达时间和服务时间,计算阻塞率和利用率。排队论研究系统中顾客和服务台的交互行为,广泛应用于通信网络、生产调度和服务行业等领域,旨在优化系统性能,减少等待时间,提高资源利用率。
|
13天前
|
存储 算法
基于HMM隐马尔可夫模型的金融数据预测算法matlab仿真
本项目基于HMM模型实现金融数据预测,包括模型训练与预测两部分。在MATLAB2022A上运行,通过计算状态转移和观测概率预测未来值,并绘制了预测值、真实值及预测误差的对比图。HMM模型适用于金融市场的时间序列分析,能够有效捕捉隐藏状态及其转换规律,为金融预测提供有力工具。
|
21天前
|
算法
基于GA遗传算法的PID控制器参数优化matlab建模与仿真
本项目基于遗传算法(GA)优化PID控制器参数,通过空间状态方程构建控制对象,自定义GA的选择、交叉、变异过程,以提高PID控制性能。与使用通用GA工具箱相比,此方法更灵活、针对性强。MATLAB2022A环境下测试,展示了GA优化前后PID控制效果的显著差异。核心代码实现了遗传算法的迭代优化过程,最终通过适应度函数评估并选择了最优PID参数,显著提升了系统响应速度和稳定性。