我如何从Python的Counter类获得加权随机选择？

我有哪里我保持的各种事情成功的轨道使用collections.Counter程序 - 的事情每个成功递增相应的计数器：我如何从Python的Counter类获得加权随机选择？

import collections 
scoreboard = collections.Counter() 

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

然后，对于以后的测试中，我想倾向于东西哪些产生了最大的成功。 Counter.elements()似乎是理想的选择，因为它返回的元素（以任意的顺序）重复的次数等于计数。所以，我想我可能只是这样做：

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

但是，没有，这引起了类型错误：类型的对象itertools.chain'没有LEN（）。好的，那么random.choice can't work with iterators。但是，在这种情况下，长度已知（或可知） - 它是sum(scoreboard.values())。

我知道通过一个未知长度的列表迭代的基本算法，并随机挑选一个元素，但我怀疑有更优雅的东西。我应该在这里做什么？

来源

2012-01-31 mattdm

如何只是把'scoreboard.elements（）'到列表中？ – delnan 2012-01-31 18:10:56

@delnan - 请参阅下面[larsks's answer]（http://stackoverflow.com/a/9084700/479426）上的评论。 – mattdm 2012-01-31 18:29:58

你可以通过使用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'

来源

2012-01-31 19:06:58

有没有直接计算项目的方法，而不是迭代“i-1”元素？如果c的值很小，这不是问题，但是如果一个或多个键的计数很高，则迭代需要很长时间。 – 2015-12-04 15:49:37

你可以包装迭代器在list()把它转换成一个列表random.choice()：

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

这里的缺点是，这种扩展列表在内存中，而不是访问它的项目，通过项目和会通常使用迭代器。

如果你想解决这个迭代，this algorithm可能是一个不错的选择。

来源

2012-01-31 18:12:16 larsks

理想情况下，我想避免将计数炸成一个巨大的列表。这样做会否定使用Counter的优点，而不是只将所有东西都堆放在一个大容器中。 – mattdm 2012-01-31 18:29:42

以下将获得一个随机项目，其中得分是多久返回该项目的权重。

import random 

def get_random_item_weighted(scoreboard):  
    total_scoreboard_value = sum(scoreboard.values()) 

    item_loc = random.random() * total_scoreboard_value 
    current_loc = 0 
    for item, score in scoreboard.items(): 
     current_loc += score 
     if current_loc > item_loc: 
      return item

举例来说，如果有2项：

物品1具有得分5
ITEM2有得分10

ITEM2会经常回来的两倍物品1

来源

2012-01-31 18:44:56 Jiaaro

另一变型与迭代：

import collections 
from collections import Counter 
import random 


class CounterElementsRandomAccess(collections.Sequence): 
    def __init__(self, counter): 
     self._counter = counter 

    def __len__(self): 
     return sum(self._counter.values()) 

    def __getitem__(self, item): 
     for i, el in enumerate(self._counter.elements()): 
      if i == item: 
       return el 

scoreboard = Counter('AAAASDFQWERQWEQWREAAAAABBBBCCDDVBSDF') 
score_elements = CounterElementsRandomAccess(scoreboard) 
for i in range(10): 
    print random.choice(score_elements)

来源

2012-01-31 19:10:46 reclosedev

另一个变型中，设置是有点麻烦，但查找是对数的复杂性（适合需要若干查找时）：

import itertools 
import random 
from collections import Counter 
from bisect import bisect 

counter = Counter({"a": 5, "b": 1, "c": 1}) 

#setup 
most_common = counter.most_common() 
accumulated = list(itertools.accumulate([x[1] for x in most_common])) # i.e. [5, 6, 7] 
total_size = accumulated[-1] 

# lookup 
i = random.randrange(total_size) 
print(most_common[bisect(accumulated, i)])

来源

2017-07-11 13:20:45 nvelan

我如何从Python的Counter类获得加权随机选择？

回答

相关问题