python - 根据值对键进行采样

Question

我在 python 中有一个字典，key->value as str->int。如果我必须根据自己的值选择一个键，那么随着值变大，该键被选择的可能性就会降低。

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

我怎样才能做到这一点？

Answer 1

如果值对于 gibler 的方法来说太大了：

建立一个元组列表(key, index)，其中index是列表中 key 之前的所有值的总和（这将是keygnibler 的列表第一次出现的索引c。同时计算所有值的总和 ( n)。

现在，生成一个x介于 0 和 之间的随机数n - 1。使用 查找列表中的最后一个条目index < x。由于列表是按索引排序的，因此您可以使用二进制搜索来有效地执行此操作。

更新： KennyTM 的代码是这个的实现，除了他使用蛮力线性搜索而不是二分搜索；如果键的数量很大，这将是低效的。

Answer 2

如果值不是太大，你可以这样做

>>> 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 3

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 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