我需要写一个加权版的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
这个函数对我来说太复杂了，而且很丑。我希望这里的每个人都能提供一些改进的建议或其他方法。对我来说，效率没有代码的整洁和可读性重要。
我可能已经来不及提供任何有用的东西了，但这里有一个简单，简短，非常有效的片段:
def choose_index(probabilies):
cmf = probabilies[0]
choice = random.random()
for k in xrange(len(probabilies)):
if choice <= cmf:
return k
else:
cmf += probabilies[k+1]
不需要排序你的概率或用你的cmf创建一个向量，它一旦找到它的选择就会终止。内存:O(1)，时间:O(N)，平均运行时间~ N/2。
如果你有权重，只需添加一行:
def choose_index(weights):
probabilities = weights / sum(weights)
cmf = probabilies[0]
choice = random.random()
for k in xrange(len(probabilies)):
if choice <= cmf:
return k
else:
cmf += probabilies[k+1]
下面是Python 3.6标准库中包含的版本:
import itertools as _itertools
import bisect as _bisect
class Random36(random.Random):
"Show the code included in the Python 3.6 version of the Random class"
def choices(self, population, weights=None, *, cum_weights=None, k=1):
"""Return a k sized list of population elements chosen with replacement.
If the relative weights or cumulative weights are not specified,
the selections are made with equal probability.
"""
random = self.random
if cum_weights is None:
if weights is None:
_int = int
total = len(population)
return [population[_int(random() * total)] for i in range(k)]
cum_weights = list(_itertools.accumulate(weights))
elif weights is not None:
raise TypeError('Cannot specify both weights and cumulative weights')
if len(cum_weights) != len(population):
raise ValueError('The number of weights does not match the population')
bisect = _bisect.bisect
total = cum_weights[-1]
return [population[bisect(cum_weights, random() * total)] for i in range(k)]
来源:https://hg.python.org/cpython/file/tip/Lib/random.py l340
下面是使用numpy的另一个版本的weighted_choice。传入weights向量，它将返回一个由0组成的数组，其中包含一个1，表示所选择的bin。该代码默认只进行一次绘制，但您可以传入绘制的数量，并且将返回每个绘制的bin的计数。
如果权重向量的和不等于1，它将被规范化，使之等于1。
import numpy as np
def weighted_choice(weights, n=1):
if np.sum(weights)!=1:
weights = weights/np.sum(weights)
draws = np.random.random_sample(size=n)
weights = np.cumsum(weights)
weights = np.insert(weights,0,0.0)
counts = np.histogram(draws, bins=weights)
return(counts[0])
假设你有
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())]
这取决于你想对分布进行多少次抽样。
假设要对分布进行K次抽样。当n是分布中的项数时，每次使用np.random.choice()的时间复杂度为O(K(n + log(n)))。
在我的例子中，我需要对相同的分布进行多次采样，阶数为10^3其中n阶数为10^6。我使用了下面的代码，它预先计算了累积分布，并在O(log(n))中对其进行采样。总体时间复杂度为O(n+K*log(n))。
import numpy as np
n,k = 10**6,10**3
# Create dummy distribution
a = np.array([i+1 for i in range(n)])
p = np.array([1.0/n]*n)
cfd = p.cumsum()
for _ in range(k):
x = np.random.uniform()
idx = cfd.searchsorted(x, side='right')
sampled_element = a[idx]
