Python加权随机

Question

我需要根据加权轮询返回不同的值，使得每20个请求中有1个收到A，1个收到B，其余的都收到C。

因此：

A => 5%
B => 5%
C => 90%

这是一个看起来可以工作的基本版本：

import random

x = random.randint(1, 100)

if x <= 5:
    return 'A'
elif x > 5 and x <= 10:
    return 'B'
else:
    return 'C'

这个算法是否正确？如果是，它能被优化吗？

- doremi

---

你可以在你的情况下使用 random.randint(1,20)。 - Akavall

@Akavall - 怎么样？(1,20)只有当A或B中的一个落入5%范围内时，才会让我进行评估，而不是两者都落入范围内，对吗？ - doremi

你的随机整数可以取值1到20，如果随机整数是1，则返回A（5%的概率），如果随机整数是2，则返回B（5%的概率），如果随机整数是其他任何值，则返回C（90%的概率）。我有遗漏什么吗？ - Akavall

六个一半打成一块。现在我想了想，你的逻辑是正确的。 - doremi

如果您希望在更一般的情况下进行研究，那么您所提到的概念是“使用反向累积分布函数方法生成随机变量”。 - Joel Cornett

Answer 1

你的算法是正确的，不过能不能来点更加优美的实现呢：

import random
my_list = ['A'] * 5 + ['B'] * 5 + ['C'] * 90
random.choice(my_list)

- jurgenreza

---

为什么不直接使用my_list = ['A'] * 5 + ['B'] * 5 + ['C'] * 90呢？ - Joel Cornett

+1，但是顺便说一句，不需要生成100个列表项，只要项目数量保持成比例即可。在这种情况下，您可以使用['A', 'B'] + ['C'] * 18。 - Joel Cornett

考虑过那个，但我认为这种方式更易读。感谢您的纠正。 - jurgenreza

在这种有限的情况下，这可能无关紧要，但一般情况下这种方法既耗时又低效。更好的解决方案是分配在 [0,1) 范围内与权重比例对应的区间，例如对于 A，分配 [0, 5/100)，对于 B 分配 [5/100, 10/100)，对于 C 分配 [10/100, 1)，并在处理如重复小数等类似事物时使用适当的近似/四舍五入，随后使用 random.random 或 random.uniform 生成随机数。 - danielm

从Python 3.6开始，您可以使用random.choices。如果您关心速度，下面的两个答案更快。 - hostingutilities.com

Answer 2

没问题。更普遍地说，您可以定义类似于以下内容：

from collections import Counter
from random import randint

def weighted_random(pairs):
    total = sum(pair[0] for pair in pairs)
    r = randint(1, total)
    for (weight, value) in pairs:
        r -= weight
        if r <= 0: return value

results = Counter(weighted_random([(1,'a'),(1,'b'),(18,'c')])
                  for _ in range(20000))
print(results)

提供

Counter({'c': 17954, 'b': 1039, 'a': 1007})

这个比例非常接近18:1:1，你可以期待这样的比例。

- andrew cooke

---

你假设输入的权重是按升序排列的。如果想要更安全，请先对输入的权重进行排序。 - Ben P

不必要 - 这种算法会对每个条目递减计数器，因此结果是相同的（从统计学上讲）。 - Luis Masuelli

补充Luis Masuelli所说的，对于任何给定的概率，相应的值范围是：数组中到该数字的所有先前元素的总和加上概率值。例如，[.05, .05, .5, .4] 大约对应于 .00-.05 | .051 - .10 | .101 - .6 | .601 - 1 范围。 - Erich

在我看来，这比被接受的答案更好。我知道 Python 代码应该追求可读性，但仅仅像这样随意地浪费内存是很疯狂的。特别是如果你要在权重不断变化的模拟中使用它的话。解释器将会构建和清理非常多的列表。 - Cruncher

Answer 3

如果你想使用加权随机而不是百分比随机，你可以创建自己的Randomizer类:

import random

class WeightedRandomizer:
    def __init__ (self, weights):
        self.__max = .0
        self.__weights = []
        for value, weight in weights.items ():
            self.__max += weight
            self.__weights.append ( (self.__max, value) )

    def random (self):
        r = random.random () * self.__max
        for ceil, value in self.__weights:
            if ceil > r: return value

w = {'A': 1.0, 'B': 1.0, 'C': 18.0}
#or w = {'A': 5, 'B': 5, 'C': 90}
#or w = {'A': 1.0/18, 'B': 1.0/18, 'C': 1.0}
#or or or

wr = WeightedRandomizer (w)

results = {'A': 0, 'B': 0, 'C': 0}
for i in range (10000):
    results [wr.random () ] += 1

print ('After 10000 rounds the distribution is:')
print (results)

- Hyperboreus

Answer 4

由于您使用了独立抽样的 uniform 随机变量，每个数字的概率都将是 1/n（n=100），因此似乎是正确的。

您可以通过运行算法大约 1000 次并查看每个字母的频率来轻松验证您的算法。

您可能还考虑另一种算法，即根据您想要的每个字母的频率生成一个包含字母的数组，并仅生成一个随机数，该随机数是数组中的索引。

这种方法在内存效率上可能不如前一种方法，但应该会更好地执行。

编辑：

为了回应 @Joel Cornett 的评论，一个示例将非常类似于 @jurgenreza，但更节省内存。

import random
data_list = ['A'] + ['B'] + ['C'] * 18
random.choice(data_list )

- iTech