随机——蓄水池抽样算法 &等概率值
2021/11/6 14:11:16
本文主要是介绍随机——蓄水池抽样算法 &等概率值,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
package ReservoirSampling import ( "math/rand" "testing" "time" ) /* 蓄水池抽样算法 假设有一个机器(以流的形式输出),它可以源源不断的吐出球, 从1号球开始吐,吐完1号球一定吐2号球,吐完2号球一定吐3号球...吐完n-1号球吐n号球, 你有一个可以装下10个球的袋子。 当前球可以进入袋子或扔掉,扔掉的球永远扔掉,就找不回来了。 当机器吐出100个球的时候,怎么保证吐出的每个球被选中的概率都是 10 /100? 1732个球被选中的概率是10/1732,3426个球被选中的概率是10/3426? 如何保证之前吐出过的所有球被选进袋子的球全均等? 不能用大容器,收集完再随机。 流程: 假设只有10个球的空间的袋子 1~10 号球,不需要决策过程,直接进袋子 往后的每个球出来的时候,以10/k的概率决定要不要他,不要他,永远都丢掉 要他,袋子中10个球等概率扔掉1个,把选中的放进来 引入一个随机函数 ,f(i) 传入i 返回 1 ~ i 等概率的数字 可以决定,吐出第k号球,1~10之外的, 我用10/k的概率,决定要或不要他 f(k) 决定要入袋子,扔谁, 袋子中10个球等概率扔一个 假如吐到17号球,3号球在袋子中的概率多少 11号球没来的时候 3号球在袋子中的概率 100% = 1 11号球来了, 11号球点儿很正 以10/11 的概率入袋子 , 3号球非常倒霉,以1/10的概率被选中,扔掉 10/11 * 1/10 = 1/11 11号球到来,3号球 仍在袋子中的概率是 1 * (1 - 1/11) = 10 / 11 12号球到来,3号球 仍在袋子中的概率是 1 * (1 - 1/12) = 11 / 12 那么 1 * 10/ 11 * 11/12 * 12 / 13 ....* 16/17 = 10 / 17 扩展 运营10亿+的游戏公司,服务器非常多,某一天全球服务器大抽奖,当天登录过的就能参与抽奖,登录次数跟结果无关, 你想选出100个幸运者,就可以用蓄水池抽样算法 需要两个参数 首次登录方法, 全球第几个登录 从一本很厚的电话簿中抽取 1000 人进行姓氏统计。 从 Google 搜索 "Ken Thompson",从中抽取 100 个结果查看哪些是今年的。 研究者只关注研究本身 */ func GetRandNumByLimit(n int) int { // return [1,n] rand.Seed(time.Now().UnixNano()) return rand.Int() % n + 1 } func TestGetRandNumByLimit(t *testing.T) { mp := map[int]int{} for i := 1; i <= 10000; i++ { mp[GetRandNumByLimit(10)]++ } t.Log(mp) } func ReservoirSampling(N int) []int { result := make([]int, N) for k := 1; k <= 1000; k++ { if k <= N { result[k - 1] = k continue } if GetRandNumByLimit(k) < N { // 天选之子 N / k result[GetRandNumByLimit(N) - 1] = k // 倒霉蛋儿 } } return result } func TestReservoirSampling(t *testing.T) { t.Log(ReservoirSampling(10)) } //给定一个等概率生成1~7的函数,如何等概率生成1~10 // f() one of [1,7] // g() -> f() one of [1,10] // 方法,最简洁的,把可以凭借的随机元,生成二进制,返回7 重做, 返回1~7 认为返回0, 返回 4~6 认为返回1 // 1~10 搞定0~9 等概率就可以 // 看看0~9需要几个二进制位, 4个二进制位就够了 // 01二进制函数,调用四次,就可以拼成 四个bit 代表的值 > 9 的重做 // f 7 ~ 13 7,8,9,10,11,12,13 制作 17 ~ 56 的等概率随机数 // 7,8,9 -> 0 // 10,11,12 -> 1 // 13 -> 重做 // 17 ~ 56 等同于 0 ~ 56 - 17 (39) 几个二进制位拼去 // _ _ _ _ _ _ > 39扔掉 重做 // 假设一个函数f, 0 , 1 返回的概率不等 0: p概率 1: 1-p概率 // 如何 0 1 等概率返回 // f 调用两次, 得到二进制状态 // 00 01 10 11 00 和 11 忽略,重做 // 得到 01 和 10 代表 0 和1 时返回 // 一生二,二生三,三生万物
这篇关于随机——蓄水池抽样算法 &等概率值的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)