最近在校论坛上看到了一个叫蓄水池(Reservoir Sampling
)抽样的问题,感觉很有趣,记录如下:
题目:要求从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
上述伪代码的意思是:先选中第1到k个元素,作为被选中的元素。然后依次对第k+1至第N个元素做如下操作:
每个元素都有k/x的概率被选中,然后等概率的(1/k)替换掉被选中的元素。其中x是元素的序号。
网上找到的证明,用数学归纳法证的:
每次都是以 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
故证明成立
自己的思考:
很多人都会想,问什么这么做呢?这种方法是怎么想到的呢?我刚开始也很困惑,后来仔细想了一遍问题,就豁然开朗了。题目中明确规定N无法确定
,这就意味着,无论N或大或小,这N个元素都要被等概率的抽取出来。那么,可以这么考虑,N是一个动态增加的数字,例如:先让你从100个元素中等概率抽取出10个元素。后来又向集合中添加了20个元素,变成了120个元素等概率抽取10个,怎么样才能随着N的动态改变而让N无论等于多少时这N个元素都等概率被抽取呢?
其实很简单,再看一眼上面的算法,第x个元素被选中的概率为k/x,这个可以等价为有x个元素,等概率抽取k个元素,每个元素被抽中的概率。也就是说,每当元素数量增加1的时候,就要对所有元素等概率抽取一次,这样当然能保证目前元素数量下是等概率抽取,这也是元素数量增加后,下次概率计算的先决条件。
分享到:
相关推荐
蓄水池算法,又称Reservoir Sampling,是一种在未知大小的大数据流中随机抽取固定数量样本的算法。在LeetCode平台上,这个算法常被用于解决实际编程挑战,例如处理大规模无序数据集的问题。这里我们主要探讨蓄水池...
另一个更为合适的策略是“蓄水池抽样”(Reservoir Sampling)。这是一种用于从大量数据中随机选取k个样本的算法。当k=1时,可以简化为每次遍历链表时,都有1/i的概率选择当前节点(其中i是遍历到的当前节点的序号)...
蓄水池算法,也称为Reservoir Sampling,是一种在未知大小的大数据流中随机抽取固定数量样本的算法。在LeetCode平台上,它可能被用于解决涉及概率抽样的问题。本项目"leetcode-ts-template"是一个专门为LeetCode挑战...
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(广度优先遍历) ...
通过设定一定的抽样比例(如T/5行数据),并采用蓄水池理论算法(reservoir sampling algorithm),实现每行数据的随机抽样。该方法允许在不重复采集的情况下,每个样本具有相同的选中概率。同时,模型还支持主动...