蓄水池抽样算法学习和应用

简介:

从一个问题引出

如何随机从n个对象中(这n个对象是按序排列的,但是在此之前你是不知道n的值的)随机选择一个对象?
具体来说,如何在实现不知道文本文件行数的情况下读取该文件,从中随机选择并输出一行?

这是《编程珠玑》中的一个习题,如果我们知道n的值,那么问题就可以简单的用一个大随机数rand()%n得到一个确切的随机位置,那么该位置的对象就是所求的对象,选中的概率是1/n。
现在并不知道n的值,
我们总是选择第一个对象,以1/2的概率选择第二个,以1/3的概率选择第三个,以此类推,以1/m的概率选择第m个对象。当该过程结束时,每一个对象具有相同的选中概率,即1/n。

针对读取文本文件的例子,我们总选择第1行,并以概率1/2选择第2行,以1/3的概率选择第3行,
依此类推,在这一过程结束时,每一行的选中概率是相等的,都是1/n,其中n是文件的总行数。

给出伪代码:

1
2
3
4
5
i= 0
while  more input lines
     with probaility  1 /++i
       choice= this  input line
print choice

这个问题可以抽象到更普遍的情况,就是蓄水池抽样问题。

 

蓄水池抽样问题

从n个元素中随机抽取k个元素,但n的个数无法事先确定。
在实际应用中,往往会遇到很大数据流的情况。因此,我们无法先保存整个数据流然后再从中选取,而是期望有一种将数据流遍历一遍就得到所选取的元素,并且保证得到的元素是随机的算法。
上面的问题就是k=1的的蓄水池抽样问题。

看一下解决蓄水池抽样问题的算法:

1.先选取n个元素中的前k个元素,保存在集合A中;

2.即从第k+1个元素开始,
每次先以k/(k+1)概率选择该元素,以k/(k+2)的概率选择第k+2个元素,
以此类推,以k/m的概率选择第j个对象(k+1<=m<=n)。
如果第m个元素被选中,则从A中随机选择一个元素并用元素m替换它;否则直接淘汰元素m;
最终每个对象被选中的概率均为k/n。

证明如下:

 

蓄水池抽样算法的典型应用

给定一个长度为N且没有重复元素的数组arr和一个整数M,实现函数等概率随机打印arr中的M个数。

首先在0~n-1中随机得到一个位置a,打印arr[a],然后把arr[a]和数组最后位置的arr[n-1]交换;
然后在0~n-2中随机得到一个位置b,然后把arr[b]和数组最后位置的arr[n-2]交换,

arr:{0,1,2,3,...,b,...,n-2},n-1,

依此类推,直到打印m个数即可。




本文转自邴越博客园博客,原文链接:http://www.cnblogs.com/binyue/p/3779186.html,如需转载请自行联系原作者
相关文章
|
26天前
|
机器学习/深度学习 人工智能 算法
探索人工智能中的强化学习:原理、算法与应用
探索人工智能中的强化学习:原理、算法与应用
|
25天前
|
机器学习/深度学习 算法 数据挖掘
C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出
本文探讨了C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出。文章还介绍了C语言在知名机器学习库中的作用,以及与Python等语言结合使用的案例,展望了其未来发展的挑战与机遇。
42 1
|
25天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
56 1
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
1月前
|
缓存 算法 网络协议
OSPF的路由计算算法:原理与应用
OSPF的路由计算算法:原理与应用
47 4
|
1月前
|
机器学习/深度学习 监控 算法
基于反光衣和检测算法的应用探索
本文探讨了利用机器学习和计算机视觉技术进行反光衣检测的方法,涵盖图像预处理、目标检测与分类、特征提取等关键技术。通过YOLOv5等模型的训练与优化,展示了实现高效反光衣识别的完整流程,旨在提升智能检测系统的性能,应用于交通安全、工地监控等领域。
|
1月前
|
存储 算法 网络协议
OSPF的SPF算法介绍:原理、实现与应用
OSPF的SPF算法介绍:原理、实现与应用
81 3
|
1月前
|
机器学习/深度学习 算法 大数据
蓄水池抽样算法详解及Python实现
蓄水池抽样是一种适用于从未知大小或大数据集中高效随机抽样的算法,确保每个元素被选中的概率相同。本文介绍其基本概念、工作原理,并提供Python代码示例,演示如何实现该算法。
34 1
|
1月前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
45 0
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR
阿里云人工智能平台 PAI 与复旦大学王鹏教授团队合作,在自然语言处理顶级会议 EMNLP 2024 上发表论文《Distilling Instruction-following Abilities of Large Language Models with Task-aware Curriculum Planning》。