Come posso ottenere una scelta casuale ponderata dalla classe Counter di Python?

Question

Ho un programma in cui sto tenendo traccia del successo delle varie cose con collections.Counter - ogni successo di una cosa incrementi del corrispondente contatore:

import collections 
scoreboard = collections.Counter() 

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

Poi, per le prove future, voglio inclinare verso cose che hanno generato il maggior successo. Counter.elements() sembrava ideale per questo, dal momento che restituisce gli elementi (in ordine arbitrario) ripetuti un numero di volte uguale al conteggio. Così ho pensato che avrei potuto solo fare:

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

Ma no, che solleva TypeError: oggetto di tipo 'itertools.chain' non ha len(). Va bene, quindi random.choice can't work with iterators. Ma, in questo caso, la lunghezza è nota (o conoscibile) - è sum(scoreboard.values()).

Conosco l'algoritmo di base per scorrere un elenco di lunghezza sconosciuta e prelevare in modo equo un elemento a caso, ma sospetto che ci sia qualcosa di più elegante. Cosa dovrei fare qui?

Answer 1

È può farlo abbastanza facilmente usando itertools.islice per ottenere l'ennesimo elemento di un iterabile:

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

Si potrebbe avvolgere l'iteratore in list() per convertirlo in una lista per random.choice():

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

Il rovescio della medaglia è che questo si espande l'elenco in memoria, piuttosto che accedervi voce per voce come farebbe normalmente si ottiene con un iteratore.

Se si desidera risolvere questo iterativamente, this algorithm è probabilmente una buona scelta.

Answer 3

Quanto segue otterrà un elemento casuale in cui il punteggio è la ponderazione per la frequenza con cui restituire quell'elemento.

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 

per esempio, se ci sono 2 articoli:

voce1 ha un punteggio 5
item2 ha un punteggio 10

item2 sarà restituito due volte più spesso voce1

Answer 4

Un'altra variante con iterazione:

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

Un'altra variante, installazione è un po 'ingombrante, ma ricerca è nella complessità logaritmica (adatta quando sono necessarie diverse ricerche):

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