Вопрос по random, python – Случайный ключ словаря Python, взвешенный по значениям

33

У меня есть словарь, где каждый ключ имеет список переменной длины, например:

<code>d = {
 'a': [1, 3, 2],
 'b': [6],
 'c': [0, 0]
}
</code>

Есть ли чистый способ получить случайный словарный ключ, взвешенный по длине его значения? random.choice(d.keys()) будет весить ключи одинаково, но в случае выше я хочу'a' должны быть возвращены примерно в половине случаев.

Возможный дубликатWeighted choice short and simple Jim G.

Ваш Ответ

8   ответов
8

Без создания нового, возможно большого списка с повторяющимися значениями:

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
Error: User Rate Limit Exceeded
1

распределение вероятностей в питоне но использует длину, чтобы установить вес. Он использует итеративную цепочку Маркова, так что ему не нужно знать, какова сумма всех весов. В настоящее время он рассчитывает максимальную длину, но если это слишком медленно, просто измените

  self._maxw = 1   

в

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

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

что ваш dict помещается в памяти, метод random.choice должен быть разумным. Но предполагая иначе, следующая техника - использовать список увеличивающихся весов и использовать разделение пополам, чтобы найти случайно выбранный вес.

>>> 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'
+1: это самое быстрое и эффективное решение; если вы предварительно вычислите «элементы» массив, он может сделать взвешенный случайный выбор за O (log | d |) времени
Возможно ли иметь словарь в Python, который не помещается в память, как связанный хеш Perl? Это интересно, но я не знаю точно, что вы имеете в виду.
словарь помещается в памяти, но этот скрипт будет работать на веб-сервере, поэтому я хочу минимизировать использование памяти hoju
Для JT и R: Диктовка не состоит из подсчетов, она уже имеет перечисляемые значения. Поэтому использование памяти перечислимым списком ключей ограничено (и, вероятно, намного меньше) самим диктом. Поэтому я просто пытался решить общую проблему с памятью, указывая на то, что, вероятно, это не проблема в данном конкретном случае.
0

чтобы придумать это. Это немного более настраиваемо. Требуется 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 за базовый код для этого.

32

Это будет работать:

random.choice([k for k in d for x in d[k]])
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceededrandom.choice([key for key, values in d.iteritems() for x in values]).
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded hoju
17

Вы всегда знаете общее количество значений в словаре? Если это так, это может быть легко сделать с помощью следующего алгоритма, который можно использовать всякий раз, когда вы хотите сделать вероятностный выбор некоторых элементов из упорядоченного списка:

  1. Iterate over your list of keys.
  2. Generate a uniformly distributed random value between 0 and 1 (aka "roll the dice").
  3. Assuming that this key has N_VALS values associated with it and there are TOTAL_VALS total values in the entire dictionary, accept this key with a probability N_VALS / N_REMAINING, where N_REMAINING is the number of items left in the list.

Преимущество этого алгоритма заключается в том, что нет необходимости создавать новые списки, что важно, если ваш словарь большой. Ваша программа платит только за цикл по ключам K для вычисления итогового значения, еще один цикл по ключам, который в среднем закончится на полпути, и сколько угодно будет сгенерировать случайное число от 0 до 1. Генерация такого случайного числа является очень распространенное приложение в программировании, поэтому большинство языков имеют быструю реализацию такой функции. В Pythonгенератор случайных чисел C реализацияАлгоритм Мерсенна Твистера, который должен быть очень быстрым. Кроме того, в документации утверждается, что эта реализация является поточно-ориентированной.

Вот код. Я уверен, что вы можете очистить его, если хотите использовать больше возможностей 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}

Изменить: Майлз указал на серьезную ошибку в моей первоначальной реализации, которая с тех пор была исправлена. Извини за это!

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceededstackoverflow.com/questions/321637/…Error: User Rate Limit Exceededcs.umd.edu/~samir/498/vitter.pdf
3

в котором каждый ключ повторяется количество раз, равное длине его значения. В вашем примере:['a', 'a', 'a', 'b', 'c', 'c'], Тогда используйтеrandom.choice().

Редактировать: или, менее элегантно, но более эффективно, попробуйте это: взять сумму длин всех значений в словаре,S (вы можете кэшировать и аннулировать это значение или обновлять его при редактировании словаря, в зависимости от того, какой именно шаблон использования вы ожидаете). Создайте случайное число от 0 до S и выполните линейный поиск по словарным ключам, чтобы найти диапазон, в который попадает ваше случайное число.

Я думаю, что это лучшее, что вы можете сделать, не меняя и не добавляя в свое представление данных.

Error: User Rate Limit Exceeded
Мои словари потенциально огромны, поэтому создание нового списка будет дорогостоящим. Есть ли более чистый способ? hoju

Похожие вопросы