我需要写一个加权版的random。选择(列表中的每个元素有不同的被选择的概率)。这是我想到的:

def weightedChoice(choices):
    """Like random.choice, but each element can have a different chance of
    being selected.

    choices can be any iterable containing iterables with two items each.
    Technically, they can have more than two items, the rest will just be
    ignored.  The first item is the thing being chosen, the second item is
    its weight.  The weights can be any numeric values, what matters is the
    relative differences between them.
    """
    space = {}
    current = 0
    for choice, weight in choices:
        if weight > 0:
            space[current] = choice
            current += weight
    rand = random.uniform(0, current)
    for key in sorted(space.keys() + [current]):
        if rand < key:
            return choice
        choice = space[key]
    return None

这个函数对我来说太复杂了,而且很丑。我希望这里的每个人都能提供一些改进的建议或其他方法。对我来说,效率没有代码的整洁和可读性重要。


当前回答

我看了指向的其他线程,并在我的编码风格中提出了这种变化,这返回了用于计数的索引,但返回字符串很简单(注释返回替代):

import random
import bisect

try:
    range = xrange
except:
    pass

def weighted_choice(choices):
    total, cumulative = 0, []
    for c,w in choices:
        total += w
        cumulative.append((total, c))
    r = random.uniform(0, total)
    # return index
    return bisect.bisect(cumulative, (r,))
    # return item string
    #return choices[bisect.bisect(cumulative, (r,))][0]

# define choices and relative weights
choices = [("WHITE",90), ("RED",8), ("GREEN",2)]

tally = [0 for item in choices]

n = 100000
# tally up n weighted choices
for i in range(n):
    tally[weighted_choice(choices)] += 1

print([t/sum(tally)*100 for t in tally])

其他回答

从版本1.7.0开始,NumPy有一个支持概率分布的选择函数。

from numpy.random import choice
draw = choice(list_of_candidates, number_of_items_to_pick,
              p=probability_distribution)

注意,probability_distribution是一个与list_of_candidate顺序相同的序列。您还可以使用关键字replace=False来更改行为,这样绘制的项就不会被替换。

从Python v3.6开始,是随机的。选项可用于从给定的填充中返回具有可选权重的指定大小的元素列表。

随机的。select (population, weights=None, *, cum_weights=None, k=1)

总体:包含独特观测值的列表。(如果为空,则引发IndexError) 权重:进行选择所需的更精确的相对权重。 Cum_weights:进行选择所需的累积权重。 K:要输出列表的大小(len)。(默认len () = 1)


一些注意事项:

1)利用加权抽样与替换,使绘制的项目以后可以被替换。权重序列中的值本身并不重要,但它们的相对比例却很重要。

np.random.choice只能将概率作为权重,也必须确保个人概率的总和达到1个标准,但这里没有这样的规定。只要它们属于数值类型(int/float/fraction, Decimal类型除外),就仍然可以执行。

>>> import random
# weights being integers
>>> random.choices(["white", "green", "red"], [12, 12, 4], k=10)
['green', 'red', 'green', 'white', 'white', 'white', 'green', 'white', 'red', 'white']
# weights being floats
>>> random.choices(["white", "green", "red"], [.12, .12, .04], k=10)
['white', 'white', 'green', 'green', 'red', 'red', 'white', 'green', 'white', 'green']
# weights being fractions
>>> random.choices(["white", "green", "red"], [12/100, 12/100, 4/100], k=10)
['green', 'green', 'white', 'red', 'green', 'red', 'white', 'green', 'green', 'green']

2)如果既没有指定weights,也没有指定cum_weights,则以等概率进行选择。如果提供了权重序列,则它必须与填充序列的长度相同。

同时指定weights和cum_weights将引发TypeError。

>>> random.choices(["white", "green", "red"], k=10)
['white', 'white', 'green', 'red', 'red', 'red', 'white', 'white', 'white', 'green']

3) cum_weights通常是itertools的结果。累加函数在这种情况下非常方便。

从文档链接: 在内部,相对权重被转换为累积权重 在进行选择之前,提供累计权重可以节省 工作。

因此,无论是提供weights=[12,12,4]还是cum_weights=[12,24,28],对于我们所设计的情况都会产生相同的结果,并且后者似乎更快/更有效。

粗糙的,但可能足够:

import random
weighted_choice = lambda s : random.choice(sum(([v]*wt for v,wt in s),[]))

这有用吗?

# define choices and relative weights
choices = [("WHITE",90), ("RED",8), ("GREEN",2)]

# initialize tally dict
tally = dict.fromkeys(choices, 0)

# tally up 1000 weighted choices
for i in xrange(1000):
    tally[weighted_choice(choices)] += 1

print tally.items()

打印:

[('WHITE', 904), ('GREEN', 22), ('RED', 74)]

假设所有权重都是整数。它们的和不一定是100,我这么做只是为了让测试结果更容易理解。(如果权重是浮点数,则将它们都乘以10,直到所有权重>= 1。)

weights = [.6, .2, .001, .199]
while any(w < 1.0 for w in weights):
    weights = [w*10 for w in weights]
weights = map(int, weights)

如果您的加权选项列表是相对静态的,并且您希望频繁采样,则可以执行一个O(N)预处理步骤,然后使用相关答案中的函数在O(1)中进行选择。

# run only when `choices` changes.
preprocessed_data = prep(weight for _,weight in choices)

# O(1) selection
value = choices[sample(preprocessed_data)][0]

一种方法是随机化所有权重的总和,然后使用这些值作为每个变量的极限点。以下是作为生成器的粗略实现。

def rand_weighted(weights):
    """
    Generator which uses the weights to generate a
    weighted random values
    """
    sum_weights = sum(weights.values())
    cum_weights = {}
    current_weight = 0
    for key, value in sorted(weights.iteritems()):
        current_weight += value
        cum_weights[key] = current_weight
    while True:
        sel = int(random.uniform(0, 1) * sum_weights)
        for key, value in sorted(cum_weights.iteritems()):
            if sel < value:
                break
        yield key