Выборка ключей по их значениям
-
21-09-2019 - |
Вопрос
У меня есть словарь в Python с ключом-> значением как str->int
.Если мне нужно выбрать ключ на основе его собственного значения, то по мере увеличения значения вероятность выбора ключа снижается.
Например, если key1=2
и key2->1
, то отношение key1
должно быть 2:1
.
Как я могу это сделать?
Решение
1. Создайте список, подобный CDF, следующим образом:
def build_cdf(distrib):
cdf = []
val = 0
for key, freq in distrib.items():
val += freq
cdf.append((val, key))
return (val, cdf)
Эта функция возвращает кортеж, первое значение — это сумма вероятностей, а второе значение — 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
Возможно, вы захотите превратить это в класс.
Другие советы
Если значения слишком велики для подхода Gnibler:
Создайте список кортежей (key, index)
, где index
— это сумма всех значений, стоящих перед ключом в списке (это будет индекс первого вхождения key
список гниблера c
.Также вычислите сумму всех значений (n
).
Теперь сгенерируйте случайное число x
между 0 и n - 1
.Найдите последнюю запись в списке с помощью index < x
.Поскольку список сортируется по индексу, вы можете эффективно использовать двоичный поиск.
Обновлять: Код KennyTM является реализацией этого, за исключением того, что он использует линейный поиск методом грубой силы вместо бинарного поиска;это будет неэффективно, если количество ключей велико.
Если значения не слишком велики, вы можете сделать это таким образом
>>> 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
Быстрая и простая версия алгоритма из ответов 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