Ключи выборки по их значениям

У меня есть словарь на Python с ключом-> значением как str->int. Если мне нужно выбрать ключ на основе его собственного значения, то по мере того, как значение становится больше, вероятность выбора ключа снижается.

Например, если key1=2 и key2->1, то отношение key1 должно быть 2:1.

Как я могу это сделать?


python dictionary sampling
person Max Frai    schedule 21.02.2010    source источник
comment
точный дубликат: stackoverflow.com/ questions / 1056151 /   -  person sth    schedule 21.02.2010

Ответы (4)


arrow_upward
1
arrow_downward

1. Создайте список, подобный CDF, следующим образом:

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

Эта функция возвращает кортеж, 1-е значение - это сумма вероятностей, а 2-е значение - это CDF.

2. Постройте сэмплер следующим образом:

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]

Использование:

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

Вы можете превратить это в класс.

person kennytm    schedule 21.02.2010

arrow_upward
2
arrow_downward

Если значения слишком велики для подхода gnibler:

Создайте список кортежей (key, index), где index - это сумма всех значений, стоящих перед ключом в списке (это будет индекс первого появления списка key gnibler c. Также вычислите сумму всех значений (n).

Теперь сгенерируйте случайное число x между 0 и n - 1. Найдите последнюю запись в списке с index < x. Поскольку список отсортирован по индексу, вы можете использовать двоичный поиск, чтобы сделать это эффективно.

Обновление: код KennyTM является его реализацией, за исключением того, что он использует линейный поиск методом перебора вместо двоичного поиска; это будет неэффективно, если количество ключей велико.

person oefe    schedule 21.02.2010
comment
+1. Это известно как выбор колеса рулетки или пропорциональный выбор пригодности и обычно используется в генетических алгоритмах. - person Dave Kirby; 21.02.2010

arrow_upward
1
arrow_downward

Если значения не слишком большие, вы можете сделать это так

>>> 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
person John La Rooy    schedule 21.02.2010

arrow_upward
0
arrow_downward

Быстрая и простая версия алгоритма из ответов oefe и 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
person sth    schedule 21.02.2010