Chaves de amostragem devido a seus valores

Question

Eu tenho um dicionário em python com key-> valor como str->int. Se eu tiver que escolher uma chave com base em seu próprio valor, à medida que o valor aumenta, a chave tem uma possibilidade menor de ser escolhido.

Por exemplo, se key1=2 e key2->1, então a atitude de key1 deveria estar 2:1.

Como posso fazer isso?

Answer 1

1. Construa uma lista do tipo CDF 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 função retorna uma tupla, o 1º valor é a soma das probabilidades e o segundo valor é o CDF.

2. Construa o amostrador como este:

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

Você pode querer transformar isso em uma aula.

Answer 2

Se os valores forem muito grandes para a abordagem de Gnibler:

Construa uma lista de tuplas (key, index), Onde index é a soma de todos os valores que vêm antes da chave na lista (esse seria o índice da primeira ocorrência de key Lista de Gnibler c. Também calcule a soma de todos os valores (n).

Agora, gerar um número aleatório xentre 0 e n - 1. Encontre a última entrada na lista com index < x. Como a lista é classificada pelo índice, você pode usar a pesquisa binária para fazer isso com eficiência.

Atualizar: O código de Kennytm é uma implementação disso, exceto que ele usa uma pesquisa linear de força bruta em vez de pesquisa binária; Isso será ineficiente se o número de chaves forem grandes.

Answer 3

Os valores não são muito grandes, você pode fazer dessa maneira

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

Uma versão rápida e simples do algoritmo das respostas da OEFE e 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