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

2024年7月10日学习笔记评论2,027字数 1191阅读3分58秒阅读模式

output

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

于是我想到了在 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 是问题的数量。

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

匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定