Reservoir Sampling 蓄水池抽样 海量数据不知道总数只能遍历一次随机抽样问题
2011年06月24日 星期五 下午 01:10
问题起源于编程珠玑Column 12中的题目10,其描述如下:
How could you select one of n objects at random, where you see the objects sequentially but you do not know the value of n beforehand? For concreteness, how would you read a text file, and select and print one random line, when you don’t know the number of lines in advance?
问题定义可以简化如下:在不知道文件总行数的情况下,如何从文件中随机的抽取一行?
首先想到的是我们做过类似的题目吗?当然,在知道文件行数的情况下,我们可以很容易的用C运行库的rand函数随机的获得一个行数,从而随机的取出一行,但是,当前的情况是不知道行数,这样如何求呢?我们需要一个概念来帮助我们做出猜想,来使得对每一行取出的概率相等,也即随机。这个概念即蓄水池抽样(Reservoir Sampling)。
有了这个概念,我们便有了这样一个解决方案:定义取出的行号为choice,第一次直接以第一行作为取出行 choice ,而后第二次以二分之一概率决定是否用第二行替换 choice ,第三次以三分之一的概率决定是否以第三行替换 choice ……,以此类推,可用伪代码描述如下:
i = 0
while more input lines
with probability 1.0/++i
choice = this input line
print choice
这种方法的巧妙之处在于成功的构造出了一种方式使得最后可以证明对每一行的取出概率都为1/n(其中n为当前扫描到的文件行数),换句话说对每一行取出的概率均相等,也即完成了随机的选取。
证明如下:
问题: 证明当前任意一行为取出行的概率为1/i,i为当前扫描到的行号,也即每一行取出的概率相等
我们用数学归纳法来证明,
当i=1时,当前只浏览了第一行,因此第一行为取出行的概率为1/1=1,符合直接取出的条件
当i=k时,有前k行为取出行的概率为1/k,我们要证明的是,当i=k+1时,前k+1行每一行被取出的概率均相等,且为1/(k+1)。当扫描到第k+1行时,我们以1/(k+1)概率替换choice,易知,第k+1行为choice的概率即为1/(k+1),对于第k行,其为choice的概率是 第k行为取出行的概率 * 第k+1行没有被取出的概率即,
对于第k行的证明同样可应用到前k-1行,对于其中第m行其为choice的概率是 第m行为取出行的概率 * 第m+1行没有被取出的概率 * … *第k+1行没有被取出的概率,即
由此证得当i=k+1时,所有行的取出概率为1/(k+1)。证毕。
回顾这个问题,我们可以对其进行扩展,即如何从未知或者很大样本空间随机地取k个数?
类比下即可得到答案,即先把前k个数放入蓄水池,对第k+1,我们以k/(k+1)概率决定是否要把它换入蓄水池,换入时随机的选取一个作为替换项,这样一直做下去,对于任意的样本空间n,对每个数的选取概率都为k/n。也就是说对每个数选取概率相等。
伪代码:
Init : a reservoir with the size: k
for i= k+1 to N
M=random(1, i);
if( M < k)
SWAP the Mth value and ith value
end for
证明我们仍然使用数学归纳法:
问题,证明对于任意样本号n,n>=k,每个样本作为取出样本的概率相等,即k/n。
证明:
当n=k时,由我们把前k个数放入蓄水池可知,每个样本的取出概率均相等,即k/k=1。 设当前样本号为n,其每个取出样本概率均相等,即为k/n,我们要证明的是这种情况对于n+1也成立。
由于我们以k/(n+1)决定是否把n+1放入蓄水池,那么对于n+1其出现在蓄水池中的概率就是k/(n+1),对于前n个元素中的任意元素m(k+1<=m<=n),其出现在蓄水池中的概率为 m出现在蓄水池中的概率 * [(m+1被选中的概率*m没被m+1替换的概率 + m+1没被选中的概率)*(m+2被选中的概率*m没被m+2替换的概率 + m+2没被选中的概率)*…*(n+1被选中的概率*m没被n+1替换的概率 + n+1没被选中的概率)],即
可见,对于n+1每个样本取出概率也相等,即为k/(n+1)。证毕。
蓄水池抽样问题是一类问题,在这里总结一下,并由衷的感叹这种方法之巧妙,不过对于这种思想产生的源头还是发觉不够,如果能够知道为什么以及怎么样想到这个解决方法的,定会更加有意义。
http://archive.cnblogs.com/a/1949762/
随即抽样问题:
要求从N个元素中随机的抽取k个元素,其中N无法确定。
是在 《计算机程序设计与艺术》 中看到的这个题目,书中只给出了解法,没给出证明。
解决方法是叫Reservoir Sampling (蓄水池抽样)
Init : a reservoir with the size: k
for i= k+1 to N
M=random(1, i);
if( M < k)
SWAP the Mth value and ith value
end for
证明:
每次都是以 k/i 的概率来选择
例: k=1000的话, 从1001开始作选择,1001被选中的概率是1000/1001,1002被选中的概率是1000/1002,与我们直觉是相符的。
接下来证明:
假设当前是i+1, 按照我们的规定,i+1这个元素被选中的概率是k/i+1,也即第 i+1 这个元素在蓄水池中出现的概率是k/i+1
此时考虑前i个元素,如果前i个元素出现在蓄水池中的概率都是k/i+1的话,说明我们的算法是没有问题的。
对这个问题可以用归纳法来证明:k < i <=N
1.当i=k+1的时候,蓄水池的容量为k,第k+1个元素被选择的概率明显为k/(k+1), 此时前k个元素出现在蓄水池的概率为 k/(k+1), 很明显结论成立。
2.假设当 j=i 的时候结论成立,此时以 k/i 的概率来选择第i个元素,前i-1个元素出现在蓄水池的概率都为k/i。
证明当j=i+1的情况:
即需要证明当以 k/i+1 的概率来选择第i+1个元素的时候,此时任一前i个元素出现在蓄水池的概率都为k/(i+1).
前i个元素出现在蓄水池的概率有2部分组成, ①在第i+1次选择前得出现在蓄水池中,②得保证第i+1次选择的时候不被替换掉
①.由2知道在第i+1次选择前,任一前i个元素出现在蓄水池的概率都为k/i
②.考虑被替换的概率:
首先要被替换得第 i+1 个元素被选中(不然不用替换了)概率为 k/i+1,其次是因为随机替换的池子中k个元素中任意一个,所以不幸被替换的概率是 1/k,故
前i个元素(池中元素)中任一被替换的概率 = k/(i+1) * 1/k = 1/i+1
则(池中元素中)没有被替换的概率为: 1 - 1/(i+1) = i/i+1
综合① ②,通过乘法规则
得到前i个元素出现在蓄水池的概率为 k/i * i/(i+1) = k/i+1
故证明成立
http://wansishuang.iteye.com/blog/443902
1. 给你一个长度为N的链表。N很大,但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个,且它们是完全随机的(出现概率均等)。
解答:
先选中前k个, 从第k+1个元素到最后一个元素为止, 以1/i (i=k+1, k+2,...,N) 的概率选中第i个元素,并且随机替换掉一个原先选中的元素, 这样遍历一次得到k个元素, 可以保证完全随机选取。这个算法叫做蓄水池抽样,在某门课上听到的,证明起来也不是很复杂。
可以参考编程珠玑问题12.10:如何从n个排序的对象中选择一个,但实现不知道n的大小?
解答:总是选择第一个对象,并使用1/2的概率选择第二个对象,使用1/3的概率选择第三个对象,以此类推。在过程结束时,每个对像被选中的概率都是1/n。伪码如下:
i = 0;
while( more objects)
{
with probability 1.0/i++
choice = this object
print choice
}
2. 给你一个数组A[1..n],请你在O(n)的时间里构造一个新的数组B[1..n],使得B[i]=A[1]*A[2]*...*A[n]/A[i]。你不能使用除法运算。
Solution:
1. 由于不知道N多大,因此不能使用[0, n]之间的等概率随机整数。遍历链表,给每个元素赋一个0到1之间的随机数作为权重(像Treap一样),最后取出权重最大的k个元素。你可以用一个堆来维护当前最大的k个数。
2. 从前往后扫一遍,然后从后往前再扫一遍。也就是说,线性时间构造两个新数组,P[i]=A[1]*A[2]*...*A[i],Q[i]=A[n]*A[n-1]*...*A[i]。于是,B[i]=P[i-1]*Q[i+1]。
分享到:
相关推荐
(1)维护一个大小为 M 的数组. 记当前接收的是第 N 个数据(这里从 1 开始,代码中从 0 开始) (2)如果 N, 直接插入(对于前 M 个元素,
今天完成题目:398print( random.uniform(1.1,5.4) ) # 产生 1.1 到 5.4 之间的随机浮点数,区间可以不是整数a=[1,
蓄水池抽样》 Blog: 《结构之法 算法之道》 Something about bit op: Something about array rotate: A Linear Time Majority Vote Algorithm 题解: Maximum Gap: Something about largest-rectangle-in-histogram:...
蓄水池算法 leetcode leetcode-cn.go 数组 267 动态规划 213 数学 190 字符串 187 树 155 深度优先搜索 132 哈希表 132 二分查找 92 贪心算法 78 广度优先搜索 74 双指针 70 栈 64 ...蓄水池抽样 2
蓄水池算法 leetcode leetcode-javascript-chimy 数据结构 1.数组 ...蓄水池抽样 3. 数学 4. 几何 5. 设计 6. 脑筋急转弯 字符串 数组 链表 队列 栈 排序 树 图 贪心算法 分治算法 回溯算法 动态规划
蓄水池算法 leetcode MyLeetCodeSummary ...蓄水池抽样 几何 Map 数组 哈希表 链表 数学 双指针 字符串 二分查找 分治算法 动态规划 回溯算法 Random Rejection Sampling Sliding Window Ordered Map Line Sweep
蓄水池算法 leetcode leetcode practice 动态规划 DynamicProgramming 贪心算法 GreedyAlgorithm 分治算法 DivideAndConquer 头脑风暴 ...蓄水池抽样 Array 数组 HashTable 哈希表 SegmenTree 线段树
这个题目有一种算法叫做蓄水池抽样,思路大致是这样的,先选中前m个, 从第m+1个元素到最后一个元素为止, 以m/i (i=m+1, m+2,...,N) 的概
技术点23 蓄水池抽样(reservoir 抽样) 4.4 本章小结 5 优化HDFS 处理大数据的技术 5.1 处理小文件 技术点24 使用Avro 存储大量小文件 5.2 通过压缩提高数据存储效率 技术点25 选择合适的压缩解码器 ...
join4.1.4 为你的数据挑选最优的合并策略4.2 排序4.2.1 二次排序技术点21 二次排序的实现4.2.2 整体并行排序技术点22 通过多个reducer 对key 进行排序4.3 抽样技术点23 蓄水池抽样(reservoir 抽样...
蓄水池JAVA 力码 旨在熟悉Java和python实现的算法和数据结构。 :) 如果你放弃,你只会输。 标签 大批 标题 解决方案 哈希表 标题 解决方案 链表 标题 解决方案 数学 标题 解决方案 细绳 标题 解决方案 两个指针 标题...
蓄水池算法leetcode 技术面试准备计划 从零开始学习数据结构和算法 如何: 数据结构:记笔记,画概念 此数据结构的算法:记笔记,绘制概念 从零开始实现数据结构及其算法 实施例程: 阅读问题说明 编写单元测试:...
leetcode双人赛 Leetcode刷题报告 目前进度是268道题了. 以及周赛还是无法做到全部AC. 与大神的差距还是较大的. ...兔子洞,蓄水池抽样。 话说,可能真的需要用个别的方式来组织这个代码了的。比如package的信息啥的。
蓄水池抽样算法 leetcode 382 更多可见算法与数据结构可见 数论 蔡勒公式 汉诺塔 计算机网络 [分组转发中的时延] [TDM, CDM, WDM, WDM, STDM] HTTP [多路复用能否取代打包工具] 编译技术 做语言的主人 Unix Linux ...
概率:洗牌算法、蓄水池抽样、蒙特卡洛 数论:素数,最小公倍数,最大公约数 位运算:异或,与的巧妙用法 特殊的数:有效数字(状态机),第n个丑数,平方数(DP解法),回文数 数字的转化:溢出检测、模拟运算...
leetcode蓄水池JAVA xiao-leetcode leet code src code, from easy to medium to hard, hahaha array backtracking(回溯) bit_manipulation breadth_first_search(深度优先遍历) depth_first_search(广度优先遍历) ...
非科班出身程序员刷题 个人刷题总结 数组问题 字符串 树 哈希表 动态规划 深度优先搜索 二分查找 贪心 双指针 广度优先搜索 栈 回溯算法 设计 链表 排序 堆 位运算 ...蓄水池抽样 二叉搜索树 记忆化
面向招聘的算法题技巧 算法题技巧 算法题(按照类型分类) ...蓄水池抽样 脑筋急转弯 记忆化 数学 几何 极小化极大 随机 扫描线算法 拒绝采样 ordered map map 了解更多欢迎关注微信公众号:科科人神