Làm cách nào để có được một lựa chọn ngẫu nhiên có trọng số từ lớp Counter của Python?

Question

tôi có một chương trình mà tôi đang theo dõi sự thành công của nhiều điều sử dụng collections.Counter - mỗi thành công của một điều increments quầy tương ứng:

import collections 
scoreboard = collections.Counter() 

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

Sau đó, đối với các bài kiểm tra trong tương lai, tôi muốn nghiêng về phía những thứ đã tạo ra thành công nhất. Counter.elements() có vẻ lý tưởng cho điều này, vì nó trả về các phần tử (theo thứ tự tùy ý) lặp lại một số lần bằng số đếm. Vì vậy, tôi figured tôi chỉ có thể làm:

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

Nhưng không, làm tăng Lỗi Loại: đối tượng của loại 'itertools.chain' không có người len(). Ok, vậy là random.choice can't work with iterators. Nhưng, trong trường hợp này, chiều dài được biết (hoặc có thể biết) - đó là sum(scoreboard.values()).

Tôi biết thuật toán cơ bản để lặp qua danh sách chiều dài không xác định và chọn ngẫu nhiên một phần tử ngẫu nhiên, nhưng tôi nghi ngờ rằng có điều gì đó thanh lịch hơn. Tôi nên làm gì ở đây?

Answer 1

Bạn có thể thực hiện điều này khá dễ dàng bằng cách sử dụng itertools.islice để nhận mục thứ N của một lần lặp lại:

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

Answer 2

Bạn có thể quấn iterator trong list() để chuyển đổi nó thành một danh sách cho random.choice():

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

Nhược điểm ở đây là điều này mở rộng danh sách trong bộ nhớ, chứ không phải truy cập vào nó item-by-item như sẽ thường nhận được với một iterator.

Nếu bạn muốn giải quyết điều này lặp đi lặp lại, this algorithm có lẽ là một lựa chọn tốt.

Answer 3

Sau đây sẽ nhận được một mục ngẫu nhiên trong đó điểm là trọng số cho tần suất trả lại mục đó.

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 

ví dụ, nếu có 2 mục:

item1 có điểm 5
ITEM2 có điểm 10

ITEM2 sẽ được trả lại gấp đôi thường xuyên như item1

Answer 4

Một biến thể với lặp:

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) 

Answer 5

biến thể khác, cài đặt là một chút rườm rà, nhưng tra cứu là về độ phức tạp logarit (phù hợp khi một số tra cứu là cần thiết):

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)])