蓄水池抽样与带面积的蓄水池抽样

导读:本篇文章讲解 蓄水池抽样与带面积的蓄水池抽样,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

蓄水池抽样背景条件

给出一个数据流,这个数据流的长度很大或者未知。并且对该数据流中数据只能访问一次。请写出一个随机选择算法,使得数据流中所有数据被选中的概率相等。

在这个背景条件下,就不能简单的采用将所有数据都加入到一个列表中然后再随机数的方式来进行随机操作,因为数据量很大,最后有多少数据是不知道的.这里采用蓄水池算法来进行计算.

介绍该算法之前,我们首先从最简单的例子出发:假设数据流只有一个数据。我们接收数据,发现数据流结束了,直接返回该数据,该数据返回的概率为1。看来很简单,那么我们试试难一点的情况:假设数据流里有两个数据。

我们读到了第一个数据,这次我们不能直接返回该数据,因为数据流没有结束。我们继续读取第二个数据,发现数据流结束了。因此我们只要保证以相同的概率返回第一个或者第二个数据就可以满足题目要求。因此我们生成一个0到1的随机数R,如果R小于0.5,我们就返回第一个数据,如果R大于0.5,返回第二个数据。

接着我们继续分析有三个数据的数据流的情况。为了方便,我们按顺序给流中的数据命名为1、2、3。我们陆续收到了数据1、2。和前面的例子一样,我们只能保存一个数据,所以必须淘汰1和2中的一个。应该如何淘汰呢?不妨和上面例子一样,我们按照二分之一的概率淘汰一个,例如我们淘汰了2。继续读取流中的数据3,发现数据流结束了,我们知道在长度为3的数据流中,如果返回数据3的概率为1/3,那么才有可能保证选择的正确性。也就是说,目前我们手里有1、3两个数据,我们通过一次随机选择,以1/3的概率留下数据3,以2/3的概率留下数据1。那么数据1被最终留下的概率是多少呢?

数据1被留下概率:(1/2)* (2/3) = 1/3
数据2被留下概率:(1/2)*(2/3) = 1/3
数据3被留下概率:1/3

这个方法可以满足题目要求,所有数据被留下返回的概率一样。

因此,循着这个思路,我们可以总结算法的过程:

假设需要采样的数量为 k 

首先构建一个可容纳 k  个元素的数组,将序列的前 k  个元素放入数组中。

然后对于第 j 个元素开始,以 k/j 的概率进行选择,是否将其替换到数组之中,当遍历完所有元素之后,就得到了所有的元素等概率选择的结果.

 

public class ReservoirSamplingTest {

    private int[] pool; // 所有数据
    private final int N = 100000; // 数据规模
    private Random random = new Random();

    @Before
    public void setUp() throws Exception {
        // 初始化
        pool = new int[N];
        for (int i = 0; i < N; i++) {
            pool[i] = i;
        }
    }

    private int[] sampling(int K) {
        int[] result = new int[K];
        for (int i = 0; i < K; i++) { // 前 K 个元素直接放入数组中
            result[i] = pool[i];
        }

        for (int i = K; i < N; i++) { // K + 1 个元素开始进行概率采样
            int r = random.nextInt(i + 1);
            // 这里其实就是k/j的体现(具体来说,当前一共r个数,r>k,而选择比k小的数的概率是k/r
//正好对应着公式中的k/r这个式子)
            if (r < K) {
                result[r] = pool[i];
            }
        }

        return result;
    }

    @Test
    public void test() throws Exception {
        for (int i : sampling(100)) {
            System.out.println(i);
        }
    }
}

带面积的蓄水池问题

非重叠矩形中的随机点icon-default.png?t=M4ADhttps://leetcode.cn/problems/random-point-in-non-overlapping-rectangles/

        给定一个由非重叠的轴对齐矩形的数组 rects ,其中 rects[i] = [ai, bi, xi, yi] 表示 (ai, bi) 是第 i 个矩形的左下角点,(xi, yi) 是第 i 个矩形的右上角角点。设计一个算法来随机挑选一个被某一矩形覆盖的整数点。矩形周长上的点也算做是被矩形覆盖。所有满足要求的点必须等概率被返回。在一个给定的矩形覆盖的空间内任何整数点都有可能被返回。请注意 ,整数点是具有整数坐标的点。

        这道题目和蓄水池问题比较相似,因为都是不知道输入的数据的数量,即长方形的数量,面积大小.而与蓄水池问题不一样的点在于,这里不是给出的一系列的随机数点,而是给出的矩形坐标,由于要求的是矩形内部的整数点,那么我们完全可以按照整数点的数量来对整个序列进行选择.

class Solution(object):

    def __init__(self, rects):
        """
        :type rects: List[List[int]]
        """
        self.rects = rects

    def pick(self):
        """
        :rtype: List[int]
        """ 
        result = []
        count = 0
        for data in self.rects:
            a0, a1, x0, x1 = data[0],data[1],data[2],data[3]
            nums = (x0 - a0 + 1) * (x1 - a1 + 1)
            count += nums
            if randrange(count) < nums:
                result = [randrange(a0,x0+1),randrange(a1, x1 + 1)]
        return result

        这里需要注意的是在求矩形内能包含多少个整数的时候,应当注意用右上角的减y值去左下角的y值,不要减反了.在result部分,右侧的随机边界是x0+1,是因为在矩形边界上的点也是应当取得的.

链表随机节点icon-default.png?t=M4ADhttps://leetcode.cn/problems/linked-list-random-node/

class Solution {
    ListNode head;
    Random random;
    public Solution(ListNode head) {
        this.head=head;
        this.random=new Random();
    }
    
    public int getRandom() {
        ListNode p=this.head;
        int count=0;
        int res=0;
        while(p!=null){
            count++;
            int randomint=random.nextInt(count)+1;//因为生成的是[0,count)的值 而不包含count  所以要加1
            if(randomint==count){
                res=p.val;
            }
            p=p.next;
        }
        return res;
    }
}

随机数索引icon-default.png?t=M4ADhttps://leetcode.cn/problems/random-pick-index/

class Solution {
    Random random = new Random();
    int[] nums;
    public Solution(int[] _nums) {
        nums = _nums;
    }
    public int pick(int target) {
        int n = nums.length, ans = 0;
        for (int i = 0, cnt = 0; i < n; i++) {
            if (nums[i] == target) {
                cnt++;
                if (random.nextInt(cnt) == 0) ans = i;
            }
        }
        return ans;
    }
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/88915.html

(0)

相关推荐

半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!