【随机算法】加权随机事件的二分查找

摘要: 加权随机事件二分的场景与解法

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

各位好，在文章 【随机算法】蒙特卡洛 中，我们了解了蒙特卡洛方法的基本思想，实现蒙特卡洛方法最重要的是根据需求正确地实现对给定分布的随机变量的采样，并学习了直接采样。

在 【随机算法】拒绝采样 中我们学习了拒绝采样，在 【随机算法】蓄水池抽样 中我们学习了蓄水池抽样，进一步在 【随机算法】加权随机事件的二分查找 中我们学习了加权蓄水池抽样。

本文我们来看加权随机事件二分的适用场景、算法流程。然后解决力扣上的两道随机算法的题目，528、497。其中 528 用加权蓄水池抽样解决过，加权随机事件二分是另一个解法。

加权随机事件二分

场景

若干个人在同一家商场进行了一些消费，每个人的消费金额为 buy[i]。

现在商场要进行一次抽奖，抽出一个幸运买家。要求中奖概率正比于消费金额。

算法

将每个人的消费金额 `buy[i]` 视为一个长度为 `buy[i]` 的区间
将所有区间连接起来，形成一个长区间，区间长度为消费金额总和 N = sum(buy)
生成 [0.0, N) 的随机实数 r
判断随机实数 r 落在哪个区间，返回对应的持有该区间的用户

记 range[i] := 第 i 个用户持有的区间左端点, 其中 range[0] = 0.0，在判断 r 落在哪个区间这一步，可以二分查找，找到 range[i] 中小于等于 r 的最大的那个。

auto it = --upper_bound(range.begin(), range.end(), r);

Follow Up

• 如果 range 还需要更新。可以上平衡树。
• 事先不用知道样本集合的大小 n 和样本权重取 m 个样本，可以用加权蓄水池抽样算法。

---

题目1

• 528. 按权重随机选择

给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。

例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

也就是说，选取下标 i 的概率为 w[i] / sum(w) 。

算法1：二分

算法流程与前面的中奖概率与消费金额成正比的问题完全一样，重点理解下面代码中的第 20 行。

class Solution {
public:
    Solution(vector<int>& w) {
        int sum = 0;
        for(int i: w) sum += i;
        int n = w.size();
        ranges.assign(n, 0.0);
        int pre_sum = w[0];
        for(int i = 1; i < n; ++i)
        {
            ranges[i] = (double)pre_sum / sum;
            pre_sum += w[i];
        }
        dre = std::default_random_engine();
        dr = std::uniform_real_distribution<double>(0.0, 1.0);
    }

    int pickIndex() {
        double p = dr(dre);
        auto it = --upper_bound(ranges.begin(), ranges.end(), p);
        return it - ranges.begin();
    }

private:
    vector<double> ranges;
    std::default_random_engine dre;
    std::uniform_real_distribution<double> dr;
};

算法2：加权蓄水池抽样

参考文章 【随机算法】加权蓄水池抽样。

题目2

• 497. 非重叠矩形中的随机点

给定一个非重叠轴对齐矩形的列表 rects，写一个函数 pick 随机均匀地选取矩形覆盖的空间中的整数点。

提示：

整数点是具有整数坐标的点。
矩形周边上的点包含在矩形覆盖的空间中。
第 i 个矩形 rects [i] = [x1，y1，x2，y2]，其中 [x1，y1] 是左下角的整数坐标，[x2，y2] 是右上角的整数坐标。
每个矩形的长度和宽度不超过 2000。
1 <= rects.length <= 100
pick 以整数坐标数组 [p_x, p_y] 的形式返回一个点。
pick 最多被调用10000次。

算法: 二分

首先从 n 个矩形中随机选择一个，然后在选中的矩形中随机选择一个点。

n 个矩形的被选概率需要与其权值成比例，权值为该矩形持有的整数点的个数。

class Solution {
public:
    Solution(vector<vector<int>>& rects) {
        int n = rects.size();
        int all = 0;
        for(const vector<int>& rect: rects)
            all += int_num(rect);
        ranges.assign(n, 0.0);
        int pre_sum = int_num(rects[0]);
        for(int i = 1; i < n; ++i)
        {
            ranges[i] = (double)pre_sum / (double)all;
            pre_sum += int_num(rects[i]);
        }
        dre = std::default_random_engine();
        dr = std::uniform_real_distribution<double>(0.0, 1.0);
        this -> rects = rects;
    }

    vector<int> pick() {
        double p = dr(dre);
        auto it = --upper_bound(ranges.begin(), ranges.end(), p);
        int rect_idx = it - ranges.begin();
        int x, y;
        pick_point(rects[rect_idx], x, y);
        return {x, y};
    }

private:
    vector<double> ranges;
    vector<vector<int>> rects;
    std::default_random_engine dre;
    std::uniform_real_distribution<double> dr;

    void pick_point(const vector<int>& rect, int& x, int& y)
    {
        int x1 = rect[0], y1 = rect[1];
        int x2 = rect[2], y2 = rect[3];
        std::uniform_int_distribution<int> di_x(x1, x2);
        x = di_x(dre);
        std::uniform_int_distribution<int> di_y(y1, y2);
        y = di_y(dre);
    }

    int int_num(const vector<int>& rect)
    {
        int w = rect[2] - rect[0] + 1;
        int h = rect[3] - rect[1] + 1;
        return w * h;
    }
};

---