El muestreo de teclas debido a sus valores

Question

Tengo un pitón con número-> valor del diccionario en el que str->int. Si tengo que elegir una clave basada en su propio valor, ya que el valor se hace más grande la llave tiene una menor posibilidad de ser elegido.

Por ejemplo, si key1=2 y key2->1, entonces la actitud de key1 debe ser 2:1.

¿Cómo puedo hacer esto?

Answer 1

1 Construir un CDF-como lista como esta:.

def build_cdf(distrib):
    cdf = []
    val = 0
    for key, freq in distrib.items():
        val += freq
        cdf.append((val, key))
    return (val, cdf)

Esta función devuelve una tupla, la primera valor es la suma de las probabilidades, y segundo valor es el CDF.

2 Construir el muestreador como esto:.

import random
def sample_from_cdf(val_and_cdf):
    (val, cdf) = val_and_cdf;
    rand = random.uniform(0, val)
    # use bisect.bisect_left to reduce search time from O(n) to O(log n).
    return [key for index, key in cdf if index > rand][0]

Uso:

x = build_cdf({"a":0.2, "b":0.3, "c":0.5});
y = [sample_from_cdf(x) for i in range(0,100000)];
print (len([t for t in y if t == "a"]))   # 19864
print (len([t for t in y if t == "b"]))   # 29760
print (len([t for t in y if t == "c"]))   # 50376

Es posible que desee hacer esto en una clase.

Answer 2

Si los valores son demasiado grandes para el enfoque de gnibler:

Construir una lista de tuplas (key, index), donde index es la suma de todos los valores que se presentan ante clave en la lista (este sería el índice de la primera aparición de la lista key c de gnibler. También calcule la suma de todos los valores (n ).

Ahora, generar un número aleatorio xbetween 0 y n - 1. Encuentra la última entrada en la lista con index < x. Dado que la lista está ordenada por el índice, se puede usar la búsqueda binaria de hacerlo de manera eficiente.

Actualización: código de KennyTM es una implementación de este, excepto que utiliza una fuerza bruta lineal en lugar de buscar búsqueda binaria; esto será ineficaz si el número de teclas son grandes.

Answer 3

los valores no son demasiado grandes, puede hacerlo de esta manera

>>> from random import choice
>>> d={"key1":2,"key2":1}
>>> c=[]
>>> for k,v in d.items():
...  c+=[k]*v
... 
>>> choice(c)
'key1'
>>> sum(1 for x in range(100) if choice(c)=="key1")
63
>>> sum(1 for x in range(100) if choice(c)=="key2")
36

Answer 4

Una versión rápida y sencilla del algoritmo de oefe de respuestas y de KennyTM:

def select_weighted(d):
   offset = random.randint(0, sum(d.itervalues())-1)
   for k, v in d.iteritems():
      if offset < v:
         return k
      offset -= v