随机Python字典的关键，通过加权值(Random Python dictionary key,

我有一本字典，其中每个键都有可变长度，例如列表：

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中的随机数生成一个C实现的梅森难题算法 ，它应该是非常快的。 此外，该文件称，这个实现是线程安全的。

下面的代码。 我敢肯定，你可以进行整理，如果您想使用更Python的特点：

#!/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:

鉴于你的字典装入内存，该random.choice方法应该是合理的。 不过，假设否则，下一个方法是使用增加权重的列表，并使用对开找到一个随机选择的重量。

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

Answer 5:

使在其中每个键被重复的次数等于其值的长度的列表。 在您的示例： ['a', 'a', 'a', 'b', 'c', 'c'] 。 然后使用random.choice()

编辑：或者，少优雅但更有效的，试试这个：走在字典中的所有值的长度的总和， S （你可以缓存和无效这个值，或保持最新的，当你编辑的字典，这取决于您预计确切的使用模式）。 产生从0至S随机数，并做通过字典键线性搜索查找到其中的随机数限制在上述范围。

我认为这是你可以在不改变或添加到您的数据表示做到最好。

Answer 6:

下面是一些代码是基于以前的答案我给了在python概率分布 ，但使用的长度设置权重。 它使用一个迭代马尔可夫链，以便它不需要知道什么总所有的权重都是。 目前，它计算的最大长度，但如果太慢只是改变

  self._maxw = 1   

至

  self._maxw = max lenght 

并删除

for k in self._odata:
     if len(self._odata[k])> self._maxw:
          self._maxw=len(self._odata[k])

下面是代码。

import random


class RandomDict:
    """
    The weight is the length of each object in the dict.
    """

    def __init__(self,odict,n=0):
        self._odata = odict
        self._keys = list(odict.keys())
        self._maxw = 1  # to increase speed set me to max length
        self._len=len(odict)
        if n==0:
            self._n=self._len
        else:
            self._n=n
        # to increase speed set above max value and comment out next 3 lines
        for k in self._odata:
            if len(self._odata[k])> self._maxw:
                self._maxw=len(self._odata[k])


    def __iter__(self):
        return self.next()

    def next(self):
        while (self._len > 0) and (self._n>0):
            self._n -= 1
            for i in range(100):
                k=random.choice(self._keys)
                rx=random.uniform(0,self._maxw)
                if rx <= len(self._odata[k]): # test to see if that is the value we want
                    break
            # if you do not find one after 100 tries then just get a random one
            yield k

    def GetRdnKey(self):
        for i in range(100):
            k=random.choice(self._keys)
            rx=random.uniform(0,self._maxw)

            if rx <= len(self._odata[k]): # test to see if that is the value we want
                break
        # if you do not find one after 100 tries then just get a random one
        return k



#test code

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


rd=RandomDict(d)

dc = {
 'a': 0,
 'b': 0,
 'c': 0
}
for i in range(100000):
    k=rd.GetRdnKey()
    dc[k]+=1

print("Key count=",dc)



#iterate over the objects

dc = {
 'a': 0,
 'b': 0,
 'c': 0
}

for k in RandomDict(d,100000):
    dc[k]+=1

print("Key count=",dc)

检测结果

Key count= {'a': 50181, 'c': 33363, 'b': 16456}
Key count= {'a': 50080, 'c': 33411, 'b': 16509}

Answer 7:

我会这样说：

random.choice("".join([k * len(d[k]) for k in d]))

这清楚地表明，在d的每个k得到尽可能多的机会作为其值的长度。 当然，它是依靠那些字符长度为1的字典键....

---

很久以后：

table = "".join([key * len(value) for key, value in d.iteritems()])
random.choice(table)

Answer 8:

我修改了一些其他的答案拿出这一点。 它更可配置一点。 它需要两个参数，一个列表和lambda函数来告诉它如何生成一个密钥。

def select_weighted(lst, weight):
   """ Usage: select_weighted([0,1,10], weight=lambda x: x) """
   thesum = sum([weight(x) for x in lst])
   if thesum == 0:
      return random.choice(lst)
   offset = random.randint(0, thesum - 1)

   for k in lst:
      v = weight(k)
      if offset < v:
         return k
      offset -= v

由于某事物为这个基本代码。

文章来源: Random Python dictionary key, weighted by values