java实现随机抽取题⽬_随机抽取样本问题蓄⽔池算法按权重
抽取问题
⾯试被问到的⼀个问题：从N个样本中随机抽取m个样本，要求每个样本被抽取的概率⼀致。升级1：要求精准抽到m个；升级2：对每个样本添加权重，要求抽取概率按照权重分配。
基础问题
问题描述：从N个样本中随机抽取m个样本，要求每个样本被抽取的概率⼀致，求怎么样抽取？数据量为百万级。
看到这个问题，最先想到的⽅法是，依次遍历每个样本，以
的概率抽中当前样本作为最后
中的⼀个，具体操作可以是：
1、每遍历⼀个样本，⽣成⼀个
之间的随机数
，对⽐
和
的⼤⼩；
2、若
⼤于
，说明属于
概率内，不抽；若
⼩于等于
，说明属于
概率内，抽它；
3、直到所有样本遍历结束。
还可以从另⼀个⾓度证明这个算法的公平性，对每个抽中的样本来说，它应该是被抽中的第
个样本，那么它被抽中的概率是：第⼀次就被抽中的概率+第⼀次没抽中第⼆次被抽中的概率+...+前
次都没抽中最后⼀次抽中的概率，⽤式⼦表⽰就是：
不考虑调⽤随机数⽣成函数的耗时的话，这样做还有个问题，那就是最后抽中的数不⼀定正好是m个，因为⼀次遍历只保证了每个样本等概率被抽中，没法保证抽到的样本量。这时⼜想到，在遍历过程中要是抽满了m个，就退出循环停⽌遍历，可是当遍历完都没有抽满m个该怎么办呢？选择再遍历⼀次的话复杂度会很⾼，也可能出现遍历了很多次都没抽满的情况。
升级问题1
问题描述：从N个样本中随机抽取m个样本，要求每个样本被抽取的概率⼀致，⽽且保证最后正好抽到m个数。
其实不算是升级问题，因为在上个问题中其实已经规定了要抽取m个，只是因为优先想到的解法出现了bug，所以不得不再重新思考。
解法1
蓄⽔池算法可以很好地解决这个问题，但这⾥先不介绍它，先介绍另⼀种同样能实现的⽅式：第
个样本，被抽中的概率是
java生成随机数的方法，
是已经抽中的样本个数。
1、第⼀个样本以概率
抽取就好；
2、若第⼀个样本没抽中，则第⼆个样本抽中概率为
；若第⼀个样本被抽中了，那么第⼆个样本抽
中的概率为
，两种情况加起来，第⼆个样本被抽中的概率为
；
3、后⾯的样本依次类推，抽中概率和当前样本序号
和已经抽中的样本数
有关，最后可以得到每个样本被抽中的概率都是
。
这个算法能够保证每个样本被抽到的概率都为
，并且最后抽到的样本为m个。关键在于，每遍历或抽到⼀个样本之后，都要对接下来抽取的概率做调整，当抽取的很快时，概率的分⼦项会变⼩，后⾯样本越来越难被抽到；当抽取的⽐较慢，概率分⼦项会变⼤，后⾯样本被抽到的概率也会变⼤。⽽且当抽满m个之后，后⾯样本被抽到的概率就为0了；当前⾯的遍历⼀直没抽满值，
中只剩下
个样本时，每个样本被抽中的概率变为1，所以怎么样都能满⾜条件。
解法2
接下来再看蓄⽔池算法，该算法是针对从⼀个长度为N的序列中随机抽取不重复的m个数，保证每个数被抽取到的概率为
这个问题⽽构建的，算法步骤为：
1、构建⼀个可放m个元素的蓄⽔池，将序列的前m个元素放⼊蓄⽔池中；
2、从第m+1个元素开始，以
的概率来决定该元素是否被替换到池⼦中；
3、当遍历完所有元素之后，蓄⽔池中的就是随机挑选出的m个元素。
算法伪代码为：
for i= m+1 to N
k=random(1, i);
if( k < m)
SWAP the kth value and ith value
end for
上述算法的证明：
对于蓄⽔池中的前m个样本，最开始被选中的概率为1，然后每个样本留到最后的概率=(m+1到n的遍历中，每次替换都抽不到⾃⼰的概率)，写成公式是
；
对于蓄⽔池之外的样本，从第m+1个开始，设序号为j，它们最终能被换到蓄⽔池中的概率=遍历到⾃⼰的时候被换进去的概率*被换进去之后不再被换出来的概率，写成公式是
因此，不论刚开始是在蓄⽔池内还是在外，最后留在蓄⽔池内的概率都是⼀样的，⽽且这个算法⼀定保证了能选出m个样本来，因为⼀开始就是基于替换的思路。
升级问题2
问题描述：从N个样本中随机抽取m个样本，要求每个样本被抽取的概率⼀致。在此基础上，为每个样本分配⼀个权重值w，范围为[1,k]，表⽰权值为k的样本被抽中的概率是权值为1的样本概率的k倍。
解法很简单，在上⾯解法1的步骤中添加⼀个权重概率就好了：第
个样本，被抽中的概率是
，
是已经抽中的样本个数,
表⽰第
个样本的权重。
1、第⼀个样本以概率
抽取就好；
2、若第⼀个样本没抽中，则第⼆个样本抽中概率为
；若第⼀个样本被抽中了，那么第⼆个样本抽中的概率为
，两种情况加起来，第⼆个样本被抽中的概率为
；
3、后⾯的样本依次类推，抽中概率和当前样本序号
和已经抽中的样本数
，以及当前样本权重有关，最后可以得到每个样本被抽中的概率都是
。
在保证每个样本等概率被抽中的基础上，再加⼊权重的影响，就能实现有概率差别地抽中。
但这⾥有个问题没想明⽩，为什么乘上去的权重概率要除以所有权重的和，直接乘以当前样本的权重
会出现什么问题？
参考⽂章

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。