Как я могу получить взвешенный случайный выбор из класса Counter Python?

У меня есть программа, в которой я отслеживаю успех различных вещей, используя collections.Counter — каждый успех вещи увеличивает соответствующий счетчик:

import collections
scoreboard = collections.Counter()

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

Затем, для будущих тестов, я хочу выбрать вещи, которые принесли наибольший успех. Counter.elements() казался идеальным для этого, так как он возвращает элементы (в произвольном порядке), повторяющиеся количество раз, равное count. Поэтому я решил, что могу просто сделать:

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

Но нет, это вызывает TypeError: у объекта типа itertools.chain нет len(). Итак, random.choice не может работать с итераторами. Но в данном случае длина известна (или известна) — это sum(scoreboard.values()).

Я знаю базовый алгоритм перебора списка неизвестной длины и справедливого случайного выбора элемента, но подозреваю, что есть что-то более элегантное. Что я должен делать здесь?


python random iterator counter weighted
person mattdm    schedule 31.01.2012    source источник
comment
Как насчет того, чтобы просто превратить scoreboard.elements() в список?   -  person    schedule 31.01.2012
comment
@delnan — см. комментарий к ответу larsks ниже.   -  person mattdm    schedule 31.01.2012

Ответы (6)


arrow_upward
7
arrow_downward

Вы можете сделать это довольно легко, используя 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'
person Felix Loether    schedule 31.01.2012
comment
Есть ли способ напрямую вычислить элемент, а не перебирать i-1 элементы? Если c имеет маленькое значение, это не проблема, но если один или несколько ключей имеют очень большое значение, итерация займет много времени. - person Brian Minton; 04.12.2015
comment
Как намекает @BrianMinton, в худшем случае время выполнения пропорционально сумме счетчиков в счетчике. Если счетчики большие, это будет очень медленно. - person Mark Amery; 26.12.2019

arrow_upward
5
arrow_downward

Учитывая словарь вариантов с соответствующими относительными вероятностями (в вашем случае это может быть счет), вы можете использовать новый random.choices добавлено в Python 3.6 следующим образом:

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)) — это именно то, что вам нужно.

person pbsds    schedule 02.02.2019

arrow_upward
3
arrow_downward

Вы можете обернуть итератор в list(), чтобы преобразовать его в список для random.choice():

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

Недостатком здесь является то, что это расширяет список в памяти, а не обращается к нему поэлементно, как это обычно происходит с помощью итератора.

Если вы хотите решить эту проблему итеративно, возможно, вам подойдет этот алгоритм.

person larsks    schedule 31.01.2012
comment
В идеале я хотел бы избежать взрыва счетчика в гигантский список. Это сводит на нет преимущество использования Counter вместо того, чтобы просто собирать все в большой контейнер. - person mattdm; 31.01.2012

arrow_upward
3
arrow_downward

Следующее получит случайный элемент, в котором оценка является весомостью того, как часто нужно возвращать этот элемент.

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
элемент 2 имеет оценку 10

item2 будет возвращаться в два раза чаще, чем item1

person Jiaaro    schedule 31.01.2012

arrow_upward
2
arrow_downward

Другой вариант, настройка немного громоздка, но поиск имеет логарифмическую сложность (подходит, когда нужно несколько поисков):

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)])
person nvelan    schedule 11.07.2017

arrow_upward
0
arrow_downward

Другой вариант с итерацией:

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)
person reclosedev    schedule 31.01.2012
comment
Это не работает для нецелочисленных подсчетов и неэффективно для очень больших подсчетов, оба из которых являются допустимыми. - person Mark Amery; 26.12.2019