随机数

随机数在实际的工作中拥有很广泛的用途。比如说，产生随机数进行验证等等。

接下来以一个力扣的题来举例：

528. 按权重随机选择

给定一个正整数数组 w ，其中 w[i] 代表位置 i 的权重，请写一个函数 pickIndex ，它可以随机地获取位置 i，选取位置 i 的概率与 w[i] 成正比。

说明:

1 <= w.length <= 10000

1 <= w[i] <= 10^5

pickIndex 将被调用不超过 10000 次

示例1:

输入:

[“Solution”,”pickIndex”]

[[[1]],[]]

输出: [null,0]

示例2:

输入:

[“Solution”,”pickIndex”,”pickIndex”,”pickIndex”,”pickIndex”,”pickIndex”]

[[[1,3]],[],[],[],[],[]]

输出: [null,0,1,1,1,0]

输入语法说明：

输入是两个列表：调用成员函数名和调用的参数。Solution 的构造函数有一个参数，即数组 w。pickIndex 没有参数。输入参数是一个列表，即使参数为空，也会输入一个 [] 空列表。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/random-pick-with-weight

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    vector<int>prob;
    int total;
    Solution(vector<int>& w) {
        total = 0;
        for(auto &index : w)
        {
            total += index;
            //这里存放的是每一个Index所占据空间的右开区间
            prob.push_back(total);
        }
    }
    int pickIndex() {
        int randval = rand() % total;
        int lo = 0, hi = prob.size() - 1;
        while(lo != hi)
        {
            int mid = (lo + hi) / 2;
            //由于是右开区间，所以当相等时，对lo赋予mid+1
            if(prob[mid] <= randval)
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo;
    }
};
/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */

在上述解法中，rand()生成的仅是伪随机数，下面我们来看看官方给出的解法
想法
让 , 其中

如果我们从 半开区间 [0,tot)中随机选择一个整数会发生什么？

是否有办法将每一个可能的整数映射到w 中一个下标，使得每个下标映射的数目与下标的权重对应呢？

是否有办法使用少于 O(tot)的空间呢？

算法

求出前缀和数组p，其中在范围[0,tot)中随机选择一个整数 targ
使用二分查找来找到下标x，其中x是满足 targ< p[x] 的最小下标。

对于某些下标i，所有满足的整数 v都映射到这个下标。因此，所有的下标都与下标权重成比例。

class Solution {
public:
    vector<int> psum;
    int tot = 0;
    //c++11 random integer generation
    mt19937 rng{random_device{}()};
    uniform_int_distribution<int> uni;

    Solution(vector<int> w) {
        for (int x : w) {
            tot += x;
            psum.push_back(tot);
        }
        uni = uniform_int_distribution<int>{0, tot - 1};
    }

    int pickIndex() {
        int targ = uni(rng);

        int lo = 0, hi = psum.size() - 1;
        while (lo != hi) {
            int mid = (lo + hi) / 2;
            if (targ >= psum[mid]) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
};

复杂度分析

• 时间复杂度：O（N）的预处理，priceIndex需要花费O（log(N)）的时间
• 空间复杂度：O（N）

在评论区中有个评论还比较有意思

Spring Cloud Ribbon （客户端负载均衡）策略中的 WeightedResponseTimeRule

此题可简述为「按权重，看作多个区间，按区间宽度越大，概率越大」

在 Ribbon 相关架构中，服务端给客户端一个服务列表，类似 Map 结构。若客户端想调用 key = serviceA，可选的具体服务端实例有 Set 的 [“/svc/a1”, “/svc/a2”, “/svc/a3”]，由客户端自行决定

Ribbon 作为客户端负载均衡来帮助客户端选择去哪个具体服务实例（a1 / a2 / a3），希望雨露均沾，又希望别运气不好抽到响应慢的服务器，故有了一种根据权重的均衡策略

权重是通过定时统计最近一段时间内，a1 / a2 / a3 各自的访问响应时间如何，如 a1: 10ms，a2: 20ms，a3: 40ms

通过算法（不赘述，有兴趣可留言喔）计算得 a1: [0, 60]，a2: (60, 110]，a3: (110, 140] 的区间对应

下次再需要访问 serviceA 时，随机一个数 [0, 140]，看落在哪个区间，就选那个实例

RabbitMQ 的 Topic 交换器使用 Trie 匹配

MySQL 中的 IN 语法涉及二分算法