У меня есть словарь, где каждый ключ имеет список переменной длины, например:
d = {
'a': [1, 3, 2],
'b': [6],
'c': [0, 0]
}
Есть ли чистый способ получить случайный ключ словаря, взвешенный по длине его значения?
random.choice(d.keys()) будет взвешивать клавиши одинаково, но в случае выше я хочу, чтобы 'a' возвращался примерно в половину времени.
Это будет работать:
random.choice([k for k in d for x in d[k]])
Вы всегда знаете общее количество значений в словаре? Если это так, это может быть легко сделать со следующим алгоритмом, который можно использовать всякий раз, когда вы хотите сделать вероятностный выбор некоторых элементов из упорядоченного списка:
Этот алгоритм имеет то преимущество, что ему не нужно создавать новые списки, что важно, если ваш словарь большой. Ваша программа платит только за цикл по К-ключам, чтобы вычислить общее количество, другой цикл над ключами, который будет в среднем заканчиваться на полпути, и что бы он ни стоил, чтобы создать случайное число между 0 и 1. Создание такого случайного числа очень распространенное приложение в программировании, поэтому большинство языков имеют быструю реализацию такой функции. В Python генератор случайных чисел реализация C алгоритм Mersenne Twister, который должен быть очень быстрым. Кроме того, в документации утверждается, что эта реализация является потокобезопасной.
Вот код. Я уверен, что вы можете очистить его, если хотите использовать больше возможностей Pythonic:
#!/usr/bin/python
import random
def select_weighted( d ):
# calculate total
total = 0
for key in d:
total = total + len(d[key])
accept_prob = float( 1.0 / total )
# pick a weighted value from d
n_seen = 0
for key in d:
current_key = key
for val in d[key]:
dice_roll = random.random()
accept_prob = float( 1.0 / ( total - n_seen ) )
n_seen = n_seen + 1
if dice_roll <= accept_prob:
return current_key
dict = {
'a': [1, 3, 2],
'b': [6],
'c': [0, 0]
}
counts = {}
for key in dict:
counts[key] = 0
for s in range(1,100000):
k = select_weighted(dict)
counts[k] = counts[k] + 1
print counts
После запуска этого 100 раз я получаю клавиши выбора этого количества раз:
{'a': 49801, 'c': 33548, 'b': 16650}
Это довольно близко к вашим ожидаемым значениям:
{'a': 0.5, 'c': 0.33333333333333331, 'b': 0.16666666666666666}
Изменить: Майлз указал на серьезную ошибку в моей первоначальной реализации, которая с тех пор была исправлена. Извините за это!
Без создания нового, возможно большого списка с повторяющимися значениями:
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
Учитывая, что ваш dict соответствует памяти, метод random.choice должен быть разумным. Но, полагая иначе, следующий метод состоит в том, чтобы использовать список увеличивающихся весов и использовать bisect для поиска случайно выбранного веса.
>>> import random, bisect
>>> items, total = [], 0
>>> for key, value in d.items():
total += len(value)
items.append((total, key))
>>> items[bisect.bisect_left(items, (random.randint(1, total),))][1]
'a'
>>> items[bisect.bisect_left(items, (random.randint(1, total),))][1]
'c'
Составьте список, в котором каждый ключ повторяется несколько раз, равный длине его значения. В вашем примере: ['a', 'a', 'a', 'b', 'c', 'c']. Затем используйте random.choice().
Изменить: или, менее элегантно, но более эффективно, попробуйте это: возьмите сумму длин всех значений в словаре, S (вы можете кэшировать и аннулировать это значение или обновлять его при редактировании словарь, в зависимости от конкретной модели использования, которую вы ожидаете). Создайте случайное число от 0 до S и выполните линейный поиск по клавишам словаря, чтобы найти диапазон, в который падает ваше случайное число.
Я думаю, что лучшее, что вы можете сделать, не изменяя или не добавляя к вашему представлению данных.
Вот некоторый код, основанный на предыдущем ответе, который я дал для распределения вероятности в python, но использует длину для установки веса. Он использует итеративную цепочку марков, так что ему не нужно знать, что такое сумма всех весов. В настоящее время он вычисляет максимальную длину, но если это слишком медленно, просто измените
self._maxw = 1
to
self._maxw = max lenght
и удалите
for k in self._odata:
if len(self._odata[k])> self._maxw:
self._maxw=len(self._odata[k])
Вот код.
import random
class RandomDict:
"""
The weight is the length of each object in the dict.
"""
def __init__(self,odict,n=0):
self._odata = odict
self._keys = list(odict.keys())
self._maxw = 1 # to increase speed set me to max length
self._len=len(odict)
if n==0:
self._n=self._len
else:
self._n=n
# to increase speed set above max value and comment out next 3 lines
for k in self._odata:
if len(self._odata[k])> self._maxw:
self._maxw=len(self._odata[k])
def __iter__(self):
return self.next()
def next(self):
while (self._len > 0) and (self._n>0):
self._n -= 1
for i in range(100):
k=random.choice(self._keys)
rx=random.uniform(0,self._maxw)
if rx <= len(self._odata[k]): # test to see if that is the value we want
break
# if you do not find one after 100 tries then just get a random one
yield k
def GetRdnKey(self):
for i in range(100):
k=random.choice(self._keys)
rx=random.uniform(0,self._maxw)
if rx <= len(self._odata[k]): # test to see if that is the value we want
break
# if you do not find one after 100 tries then just get a random one
return k
#test code
d = {
'a': [1, 3, 2],
'b': [6],
'c': [0, 0]
}
rd=RandomDict(d)
dc = {
'a': 0,
'b': 0,
'c': 0
}
for i in range(100000):
k=rd.GetRdnKey()
dc[k]+=1
print("Key count=",dc)
#iterate over the objects
dc = {
'a': 0,
'b': 0,
'c': 0
}
for k in RandomDict(d,100000):
dc[k]+=1
print("Key count=",dc)
Результаты тестов
Key count= {'a': 50181, 'c': 33363, 'b': 16456}
Key count= {'a': 50080, 'c': 33411, 'b': 16509}
Я бы сказал это:
random.choice("".join([k * len(d[k]) for k in d]))
Это дает понять, что каждый k из d получает столько же шансов, сколько длина его значения. Конечно, он полагается на словарные ключи длиной 1, которые являются символами....
Много позже:
table = "".join([key * len(value) for key, value in d.iteritems()])
random.choice(table)
Я изменил некоторые другие ответы, чтобы придумать это. Это немного более настраиваемо. Для генерации ключа требуется 2 аргумента, список и функция лямбда.
def select_weighted(lst, weight):
""" Usage: select_weighted([0,1,10], weight=lambda x: x) """
thesum = sum([weight(x) for x in lst])
if thesum == 0:
return random.choice(lst)
offset = random.randint(0, thesum - 1)
for k in lst:
v = weight(k)
if offset < v:
return k
offset -= v
Благодаря sth для базового кода для этого.