我需要写一个加权版的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, 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
在Udacity免费课程AI for Robotics中，Sebastien Thurn对此进行了演讲。基本上，他用mod运算符%做了一个权重索引的圆形数组，将变量beta设为0，随机选择一个索引，
for循环遍历N，其中N是指标的数量，在for循环中，首先按公式增加beta:
Beta = Beta +来自{0…2 * Weight_max}
然后在for循环中嵌套一个while循环per:
while w[index] < beta:
beta = beta - w[index]
index = index + 1
select p[index]
然后到下一个索引，根据概率(或课程中介绍的情况下的归一化概率)重新采样。
在Udacity上找到第8课，机器人人工智能的第21期视频，他正在讲粒子滤波器。
将权重排列成a
累积分布。
使用random.random()来选择一个随机的
浮点0.0 <= x < total。
搜索
用等分法进行分布。二等分的
如http://docs.python.org/dev/library/bisect.html#other-examples中的示例所示。
from random import random
from bisect import bisect
def weighted_choice(choices):
values, weights = zip(*choices)
total = 0
cum_weights = []
for w in weights:
total += w
cum_weights.append(total)
x = random() * total
i = bisect(cum_weights, x)
return values[i]
>>> weighted_choice([("WHITE",90), ("RED",8), ("GREEN",2)])
'WHITE'
如果需要做出多个选择，可以将其分成两个函数，一个用于构建累积权重，另一个用于对随机点进行等分。
如果你有一个加权字典而不是一个列表，你可以这样写
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 ']
