random.choice的加权版本

我需要写一个加权版的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

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

当前回答

如果您的加权选项列表是相对静态的，并且您希望频繁采样，则可以执行一个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]

2015-04-21 17:42:55

其他回答

def weighted_choice(choices):
   total = sum(w for c, w in choices)
   r = random.uniform(0, total)
   upto = 0
   for c, w in choices:
      if upto + w >= r:
         return c
      upto += w
   assert False, "Shouldn't get here"

2010-09-09 19:08:40

如果你有一个加权字典而不是一个列表，你可以这样写

items = { "a": 10, "b": 5, "c": 1 } 
random.choice([k for k in items for dummy in range(items[k])])

注意(k, k范围的虚拟物品(物品[k])]产生这个列表(' a ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' c ', ' b ', ' b ', ' b ', ' b ', ' b ']

2012-05-18 15:49:08

通解:

import random
def weighted_choice(choices, weights):
    total = sum(weights)
    treshold = random.uniform(0, total)
    for k, weight in enumerate(weights):
        total -= weight
        if total < treshold:
            return choices[k]

2013-06-09 15:26:44

我不喜欢它们的语法。我只想具体说明这些项目是什么以及每项的权重是多少。我意识到我可以用随机。选项，但我很快就写了下面的类。

import random, string
from numpy import cumsum

class randomChoiceWithProportions:
    '''
    Accepts a dictionary of choices as keys and weights as values. Example if you want a unfair dice:


    choiceWeightDic = {"1":0.16666666666666666, "2": 0.16666666666666666, "3": 0.16666666666666666
    , "4": 0.16666666666666666, "5": .06666666666666666, "6": 0.26666666666666666}
    dice = randomChoiceWithProportions(choiceWeightDic)

    samples = []
    for i in range(100000):
        samples.append(dice.sample())

    # Should be close to .26666
    samples.count("6")/len(samples)

    # Should be close to .16666
    samples.count("1")/len(samples)
    '''
    def __init__(self, choiceWeightDic):
        self.choiceWeightDic = choiceWeightDic
        weightSum = sum(self.choiceWeightDic.values())
        assert weightSum == 1, 'Weights sum to ' + str(weightSum) + ', not 1.'
        self.valWeightDict = self._compute_valWeights()

    def _compute_valWeights(self):
        valWeights = list(cumsum(list(self.choiceWeightDic.values())))
        valWeightDict = dict(zip(list(self.choiceWeightDic.keys()), valWeights))
        return valWeightDict

    def sample(self):
        num = random.uniform(0,1)
        for key, val in self.valWeightDict.items():
            if val >= num:
                return key

2019-07-31 21:53:38

假设你有

items = [11, 23, 43, 91] 
probability = [0.2, 0.3, 0.4, 0.1]

你有一个函数，它生成一个介于[0,1)之间的随机数(我们可以在这里使用random.random())。现在求概率的前缀和

prefix_probability=[0.2,0.5,0.9,1]

现在，我们只需取一个0-1之间的随机数，然后使用二分搜索来查找该数字在prefix_probability中的位置。这个索引就是你的答案

代码是这样的

return items[bisect.bisect(prefix_probability,random.random())]

2022-11-29 07:35:14

random.choice的加权版本

推荐文章

最新文章

标签