美文网首页常见算法题
蓄水池抽样算法

蓄水池抽样算法

作者: wengle | 来源:发表于2017-10-26 17:02 被阅读0次

问题描述

给出一个数据流,这个数据流的长度很大或者未知(内存无法一次性容纳下),并且对该数据流中数据只能访问一次。
简而言之:要求从N个元素中随机的抽取k个元素,其中N的大小未知,k >= 1。
请写出一个随机选择算法,使得数据流中所有数据被选中的概率相等。

算法思路

先初始化一个集合,集合中有k个元素,将此集合作为蓄水池(reservoir),然后从第k+1个元素开始遍历,并且按一定的概率替换掉蓄水池里面的元素。

《The Art of Computer Programming》中的伪代码
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个数取出来放入蓄水池中,然后从第k+1个数开始遍历。假设遍历到第i个数,以k/i的概率替换掉蓄水池中的某个元素即可。

数学归纳法证明

假设i=n时,前k个元素都以k/n被选中;
那么当i=n+1是,第n+1个元素被选中的概率为k/n+1;
对于前面的n个元素,每个元素被选中的情况分为两种:
1.前面n次已经被选中,第n+1次时,第n+1个元素没有被选中;
2.前面n次已经被选中,第n+1次时,第n+1个元素被选中但是没有将其替换掉;
此时的概率为: k/n×(1−k/n+1)+k/n×(k/n+1×(1−1/k))=k/n+1
由此可见,第n+1步也满足假设条件,问题得到证明。

Java代码实现

    public static List<Integer> reservior(int k){
        List<Integer> raw = getRandomList(1, 100000);
        List<Integer> res = new ArrayList<Integer>(k);
        for(int i = 0; i < k; i++){
            res.add(raw.get(i));
        }
        for(int i = k; i < raw.size(); i++){
            int m = rand(0,i);
            if(m < k){
                swap(res.get(m), raw.get(i));
            }
        }
        return res;
    }

    private static List<Integer> getRandomList(int start, int end) {
        List<Integer> res = new ArrayList<Integer>();
        for (int i = start; i <= end; i++) {
            res.add(i);
        }
        for (int i = 0; i < lens; i++) {
            int t = rand(i, lens);
            swap(res.get(i), res.get(t));
        }
        return res;
    }

相关文章

  • 蓄水池抽样算法(Reservoir Sampling)

    蓄水池抽样算法(Reservoir Sampling) 许多年以后,当听说蓄水池抽样算法时,邱simple将会想起...

  • 2021-02-01 蓄水池抽样算法(Reservoir Sam

    蓄水池抽样算法(Reservoir Sampling)[https://www.jianshu.com/p/7a9...

  • 蓄水池抽样算法

    问题描述 给出一个数据流,这个数据流的长度很大或者未知(内存无法一次性容纳下),并且对该数据流中数据只能访问一次。...

  • 蓄水池抽样算法

    面试题: 如果有一个文件很大,内存很大,不知道有多少行。你的任务是随机输出一行。文件只能遍历一次。解析:算法就是需...

  • 蓄水池抽样算法

    蓄水池算法 给定一个数据流,数据流长度N很大,且N直到处理完所有数据之前都不可知,请问如何在只遍历一遍数据(O(N...

  • 算法笔记之蓄水池抽样算法

    问题描述 从一个无法确定规模的数据流 N 中,随机抽取 k 个样本。 算法过程 创建一个大小为 k 的抽样数组; ...

  • 蓄水池抽样算法(Reservoir Sampling)

    https://www.jianshu.com/p/7a9ea6ece2af[https://www.jiansh...

  • 蓄水池抽样-reservoir

    蓄水池抽样是在O(n)复杂度下随机从海量动态的数据流中取m个数据的一种算法,常在机器学习中使用。 以下是对蓄水池抽...

  • 蓄水池抽样

    蓄水池抽样,首先有它的应用和它的神奇之处,其次这个也是机器学习领域面试的热门试题。 问题一(引子):流式数据(St...

  • (转)蓄水池抽样算法(Reservoir Sampling)

    从一个包含n个对象的列表S中随机选取k个对象,n为一个非常大或者不知道的值。通常情况下,n是一个非常大的值,大到无...

网友评论

    本文标题:蓄水池抽样算法

    本文链接:https://www.haomeiwen.com/subject/sqskpxtx.html