随机Python字典键,按值加权

Question

我有一个字典,其中每个键都有一个可变长度列表,例如:

d = {
 'a': [1, 3, 2],
 'b': [6],
 'c': [0, 0]
}

是否有一种干净的方法来获取随机字典键,按其值的长度加权？ random.choice(d.keys())将对键进行相同的加权,但在上面的情况下,我希望'a'大约一半的时间返回.

Answer 1

这可行:

random.choice([k for k in d for x in d[k]])

Answer 2

你总是知道字典里的值总数吗？如果是这样,使用以下算法可能很容易,只要您想从有序列表中对某些项进行概率选择,就可以使用该算法:

1. 迭代你的密钥列表.
2. 生成介于0和1之间的均匀分布的随机值(也称为"掷骰子").
3. 假设这个键有与之相关联的N_VALS值,并有TOTAL_VALS整个词典总价值,接受概率N_VALS/N_REMAINING,其中N_REMAINING是留在列表中的项目数这一关键.

该算法的优点是不必生成任何新列表,如果您的字典很大,这很重要.你的程序只需支付K键上的循环来计算总数,另外一个键上的循环将平均结束一半,以及生成0到1之间的随机数的成本.生成这样一个随机数是在编程中非常常见的应用程序,因此大多数语言都可以快速实现这样的功能.在Python中,随机数生成器是Mersenne Twister算法的C实现,应该非常快.此外,文档声称此实现是线程安全的.

这是代码.如果你想使用更多的Pythonic功能,我相信你可以清理它:

#!/usr/bin/python

import random

def select_weighted( d ):
   # calculate total
   total = 0
   for key in d:
      total = total + len(d[key])
   accept_prob = float( 1.0 / total )

   # pick a weighted value from d
   n_seen = 0
   for key in d:
      current_key = key
      for val in d[key]:
         dice_roll = random.random()
         accept_prob = float( 1.0 / ( total - n_seen ) )
         n_seen = n_seen + 1
         if dice_roll <= accept_prob:
            return current_key

dict = {
   'a': [1, 3, 2],
   'b': [6],
   'c': [0, 0]
}

counts = {}
for key in dict:
   counts[key] = 0

for s in range(1,100000):
   k = select_weighted(dict)
   counts[k] = counts[k] + 1

print counts

运行100次后,我得到了这么多次选择键:

{'a': 49801, 'c': 33548, 'b': 16650}

这些非常接近您的预期值:

{'a': 0.5, 'c': 0.33333333333333331, 'b': 0.16666666666666666}

编辑:迈尔斯在我的原始实现中指出了一个严重错误,该错误已经得到纠正.对于那个很抱歉!

Answer 3

没有构建具有重复值的新的可能大的列表:

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

Answer 4

鉴于你的dict适合记忆,random.choice方法应该是合理的.但假设不然,下一个技术是使用增加权重的列表,并使用bisect来找到随机选择的权重.

>>> import random, bisect
>>> items, total = [], 0
>>> for key, value in d.items():
        total += len(value)
        items.append((total, key))


>>> items[bisect.bisect_left(items, (random.randint(1, total),))][1]
'a'
>>> items[bisect.bisect_left(items, (random.randint(1, total),))][1]
'c'