采样键，由于它们的值

Question

我有一个字典在python与键 - >值作为str->int。如果我要选择基于它自身价值的关键，那么作为值变大的主要有被选择的可能性较低。

例如，如果key1=2和key2->1，然后key1的态度应该是2:1。

我怎样才能做到这一点？

Answer 1

<强> 1 构造一个CDF状这样列表：

def build_cdf(distrib):
    cdf = []
    val = 0
    for key, freq in distrib.items():
        val += freq
        cdf.append((val, key))
    return (val, cdf)

此函数返回的元组，所述第一值是概率的总和，和第二值是CDF。

<强> 2 构建采样这样的：

import random
def sample_from_cdf(val_and_cdf):
    (val, cdf) = val_and_cdf;
    rand = random.uniform(0, val)
    # use bisect.bisect_left to reduce search time from O(n) to O(log n).
    return [key for index, key in cdf if index > rand][0]

用法：

x = build_cdf({"a":0.2, "b":0.3, "c":0.5});
y = [sample_from_cdf(x) for i in range(0,100000)];
print (len([t for t in y if t == "a"]))   # 19864
print (len([t for t in y if t == "b"]))   # 29760
print (len([t for t in y if t == "c"]))   # 50376

您可能要制作成一类这个。

Answer 2

如果该值过大gnibler的做法：

构建元组(key, index)，其中index是列表键之前来的所有值的总和的列表（这将是key gnibler的名单c的第一次出现的索引。另外计算所有值的总和（n ）。

现在，生成一个随机数xbetween 0和n - 1。查找与index < x列表中的最后一项。由于名单是由指数排序，您可以使用二进制搜索做有效。

<强>更新 KennyTM的代码就是一个这样的实施方式中，不同之处在于，他使用蛮力的线性搜索而不是二进制搜索;这将是低效的，如果键的数目是大的。

Answer 3

它的值不是太大，你可以做这样

>>> from random import choice
>>> d={"key1":2,"key2":1}
>>> c=[]
>>> for k,v in d.items():
...  c+=[k]*v
... 
>>> choice(c)
'key1'
>>> sum(1 for x in range(100) if choice(c)=="key1")
63
>>> sum(1 for x in range(100) if choice(c)=="key2")
36

Answer 4

这oefe的算法的快速和简单的版本和KennyTM的回答：

def select_weighted(d):
   offset = random.randint(0, sum(d.itervalues())-1)
   for k, v in d.iteritems():
      if offset < v:
         return k
      offset -= v