如何从Python的Counter类中获取加权随机选择？

Question

我有一个程序，用来记录各种事情的成功情况，我是通过collections.Counter来实现的——每当某个事情成功时，相应的计数器就会加一：

import collections
scoreboard = collections.Counter()

if test(thing):
    scoreboard[thing]+ = 1

接下来，在未来的测试中，我想更倾向于那些成功次数最多的事情。我觉得Counter.elements()非常适合这个需求，因为它会返回所有元素（顺序不固定），每个元素的出现次数和它的计数相等。所以我想我可以这样做：

import random
nextthing=random.choice(scoreboard.elements())

但是不行，这样会报错TypeError: object of type 'itertools.chain' has no len()。好吧，random.choice不能和迭代器一起使用。不过，在这种情况下，长度是已知的（或者可以知道）——就是sum(scoreboard.values())。

我知道一个基本的算法，可以用来遍历一个未知长度的列表，并公平地随机选择一个元素，但我觉得可能还有更优雅的方法。我应该怎么做呢？

Answer 1

你可以把这个迭代器用 list() 包裹起来，这样就能把它转换成一个列表，方便用 random.choice() 来随机选择。

nextthing = random.choice(list(scoreboard.elements()))

不过这样做的缺点是，它会把整个列表都加载到内存里，而不是像通常使用迭代器那样一个一个地访问每个元素。

如果你想用迭代的方式来解决这个问题，这个算法可能是个不错的选择。

Answer 2

给定一个包含选择和相应概率的字典（在你的情况下可以是计数），你可以使用Python 3.6中新增的random.choices，用法如下：

import random

my_dict = {
    "choice a" : 1, # will in this case be chosen 1/3 of the time
    "choice b" : 2, # will in this case be chosen 2/3 of the time
}

choice = random.choices(*zip(*my_dict.items()))[0]

对于你使用的Counter代码，你也可以这样做，因为Counter同样有items()这个方法。

import collections
import random

my_dict = collections.Counter(a=1, b=2, c=3)
choice = random.choices(*zip(*my_dict.items()))[0]

解释一下：my_dict.items()的结果是[('a', 1), ('b', 2), ('c', 3)]。
所以zip(*my_dict.items())的结果是[('a', 'b', 'c'), (1, 2, 3)]。
而random.choices(('a', 'b', 'c'), (1, 2, 3))正是你想要的结果。

Answer 3

你可以很简单地使用 itertools.islice 来获取一个可迭代对象中的第 N 个项目：

>>> import random
>>> import itertools
>>> import collections
>>> c = collections.Counter({'a': 2, 'b': 1})
>>> i = random.randrange(sum(c.values()))
>>> next(itertools.islice(c.elements(), i, None))
'a'