¿Cómo puedo obtener una selección aleatoria ponderada de la clase de contador de Python?

Question

tengo un programa en el que estoy no perder de vista el éxito de varias cosas usando collections.Counter - cada éxito de una cosa incrementa el contador correspondiente:

import collections 
scoreboard = collections.Counter() 

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

Entonces, para las pruebas futuras, quiero inclinar hacia cosas que han generado el mayor éxito. Counter.elements() parecía ideal para esto, ya que devuelve los elementos (en orden arbitrario) repetidos varias veces igual al conteo. Así que pensé que sólo podía hacer:

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

Pero no, eso plantea TypeError: objeto de tipo 'itertools.chain' no tiene len(). De acuerdo, entonces random.choice can't work with iterators. Pero, en este caso, la longitud es conocida (o cognoscible): es sum(scoreboard.values()).

Conozco el algoritmo básico para iterar a través de una lista de longitud desconocida y escoger un elemento al azar, pero sospecho que hay algo más elegante. ¿Qué debería estar haciendo aquí?

Answer 1

Usted puede hacer esto fácilmente usando itertools.islice para obtener el enésimo elemento de un iterable:

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

Se puede envolver el iterador en list() para convertirlo en una lista de random.choice():

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

La desventaja aquí es que este se expande la lista en la memoria, en vez de ingresar elemento por elemento como lo haría normalmente obtener con un iterador.

Si desea resolver esto de forma iterativa, this algorithm es probablemente una buena opción.

Answer 3

Lo siguiente obtendrá un elemento aleatorio donde la puntuación es la ponderación de la frecuencia con la que se debe devolver ese artículo.

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 

por ejemplo, si hay 2 artículos:

elemento1 tiene una puntuación de 5
elemento2 tiene una puntuación de 10

elemento2 será devuelto dos veces más que elemento1

Answer 4

Otra variante con iteración:

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

Otra variante, configuración es un poco engorroso, pero las operaciones de búsqueda se encuentra en la complejidad logarítmica (ideal cuando se necesitan varias operaciones de búsqueda):

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