实现基于权重的随机选择算法

今天我在做一款应用时，需要随机抽取问题，但是我不希望问题出现的概率是一样的，面对这种需求该如何解决呢？

于是我想到了在 Nginx 中，实现负载均衡时，可以给每个服务分别设置权重值，来实现自定义服务被选中的概率。

那么，我如果想自定义问题被选择的概率，是不是也只需要给每个问题设置权重值即可。

输入random+weight，谷歌一下，才发现其实 python 的随机模块已经实现自定义权重值了，而且调用很简单，类似这样即可：

import random

# 问题列表和对应的权重值
questions = ["问题1", "问题2", "问题3", "问题4"]
weights = [0.1, 0.3, 0.4, 0.2]

# 使用 random.choices 进行随机抽取
selected_question = random.choices(questions, weights, k=1)[0]

print(f"抽取到的问题是: {selected_question}")

那么，如果我想自己实现这个算法，可以怎么做呢？

可以分为以下几步：

1.

构建累积权重数组：

• 首先，我们构建一个累积权重数组。这个数组中的每个元素是到当前元素为止所有权重的累积和。
• 例如，如果权重数组是 [0.1, 0.3, 0.4, 0.2]，那么累积权重数组是 [0.1, 0.4, 0.8, 1.0]。

2.

生成一个随机数：

生成一个在 0 到累积权重数组最大值（在这种情况下是 1.0）之间的随机数。

3.

二分查找：

• 使用生成的随机数在累积权重数组中进行查找，确定它落在哪个区间中。
• 这个区间对应的就是被选中的问题。

明白了实现，写代码就简单了：

（这里仅仅实现权重算法，为了方便，代码中还是用到了随机选择和二分查找函数）

import random
import bisect

# 问题列表和对应的权重值
questions = ["问题1", "问题2", "问题3", "问题4"]
weights = [0.1, 0.3, 0.4, 0.2]

# 计算累积权重数组
cumulative_weights = []
cumulative_sum = 0

for weight in weights:
    cumulative_sum += weight
    cumulative_weights.append(cumulative_sum)

# 生成一个随机数
random_number = random.random() * cumulative_sum

# 使用二分查找来确定随机数落在哪个区间
index = bisect.bisect(cumulative_weights, random_number)

# 选中的问题
selected_question = questions[index]

print(f"抽取到的问题是: {selected_question}")

这种方法的时间复杂度主要取决于二分查找部分，为 O(log n)，其中 n 是问题的数量。

那么二分查找算法该如何实现呢？有空我们继续探索……