Взвешенная версия random.choice

Мне нужно было написать взвешенную версию random.choice (каждый элемент в списке имеет другую вероятность выбора). Вот что я придумал:

def weightedChoice(choices): """Like random.choice, but each element can have a different chance of being selected. choices can be any iterable containing iterables with two items each. Technically, they can have more than two items, the rest will just be ignored. The first item is the thing being chosen, the second item is its weight. The weights can be any numeric values, what matters is the relative differences between them. """ space = {} current = 0 for choice, weight in choices: if weight > 0: space[current] = choice current += weight rand = random.uniform(0, current) for key in sorted(space.keys() + [current]): if rand < key: return choice choice = space[key] return None 

Эта функция кажется мне слишком сложной и уродливой. Я надеюсь, что все здесь могут предложить некоторые предложения по его улучшению или альтернативные способы сделать это. Эффективность не так важна для меня, как чистота кода и его удобочитаемость.

  • Методы работы с большими массивами Numpy?
  • Эквивалентность Python для встроенных функций или макросов
  • Python App Engine webapp2 медленный путь
  • Преобразование 1,2 Гбайт списка ребер в разреженную матрицу
  • Сбой при оптимизации последовательности строк в CPython
  • Как я могу оптимизировать этот код Python для генерации всех слов со словом-расстоянием 1?
  • Python: вычислять относительный путь из одного каталога в другой
  • Создавая список значений, соответствие regex COULD в Python
  • Как удалить консоли Windows из порожденных процессов в Python (2.7)?
  • Как я могу визуализировать древовидную структуру (рекурсивную) с использованием шаблона django?
  • Почему я вижу «TypeError: строковые индексы должны быть целыми»?
  • В Inline «open and write file» подразумевается закрытие ()?
  • 16 Solutions collect form web for “Взвешенная версия random.choice”

     def weighted_choice(choices): total = sum(w for c, w in choices) r = random.uniform(0, total) upto = 0 for c, w in choices: if upto + w >= r: return c upto += w assert False, "Shouldn't get here" 

    Начиная с версии 1.7.0, NumPy имеет функцию choice которая поддерживает распределения вероятностей.

     from numpy.random import choice draw = choice(list_of_candidates, number_of_items_to_pick, p=probability_distribution) 

    Обратите внимание, что list_of_candidates представляет собой последовательность в том же порядке list_of_candidates . Вы также можете использовать ключевое слово replace=False чтобы изменить поведение, чтобы нарисованные элементы не были заменены.

    1. Упорядочить веса в кумулятивное распределение.
    2. Используйте random.random (), чтобы выбрать случайный float 0.0 <= x < total .
    3. Найдите распределение, используя bisect.bisect, как показано в примере на странице http://docs.python.org/dev/library/bisect.html#other-examples .
     from random import random from bisect import bisect def weighted_choice(choices): values, weights = zip(*choices) total = 0 cum_weights = [] for w in weights: total += w cum_weights.append(total) x = random() * total i = bisect(cum_weights, x) return values[i] >>> weighted_choice([("WHITE",90), ("RED",8), ("GREEN",2)]) 'WHITE' 

    Если вам нужно сделать несколько вариантов, разделите их на две функции: одну, чтобы собрать кумулятивные веса, а другую – делить пополам на случайную точку.

    Итак, с Python3.6 есть choices метода из random модуля.

     Python 3.6.1 (v3.6.1:69c0db5050, Mar 21 2017, 01:21:04) Type 'copyright', 'credits' or 'license' for more information IPython 6.0.0 -- An enhanced Interactive Python. Type '?' for help. In [1]: import random In [2]: population = [['a','b'], ['b','a'], ['c','b']] In [3]: list_of_prob = [0.2, 0.2, 0.6] In [4]: population = random.choices(population, weights=list_of_prob, k=10) In [5]: population Out[5]: [['c', 'b'], ['c', 'b'], ['b', 'a'], ['c', 'b'], ['c', 'b'], ['b', 'a'], ['c', 'b'], ['b', 'a'], ['c', 'b'], ['c', 'b']] 

    И люди также упомянули, что есть numpy.random.choice которые поддерживают весы, НО это не поддерживает 2d массивы и так далее.

    Итак, в основном вы можете получить все, что хотите, с помощью random.choices если у вас есть 3.6.x Python.

    Если вы не против использования numpy, вы можете использовать numpy.random.choice .

    Например:

     import numpy items = [["item1", 0.2], ["item2", 0.3], ["item3", 0.45], ["item4", 0.05] elems = [i[0] for i in items] probs = [i[1] for i in items] trials = 1000 results = [0] * len(items) for i in range(trials): res = numpy.random.choice(items, p=probs) #This is where the item is selected! results[items.index(res)] += 1 results = [r / float(trials) for r in results] print "item\texpected\tactual" for i in range(len(probs)): print "%s\t%0.4f\t%0.4f" % (items[i], probs[i], results[i]) 

    Если вы знаете, сколько вариантов вам нужно сделать заранее, вы можете сделать это без цикла:

     numpy.random.choice(items, trials, p=probs) 

    Сырой, но может быть достаточно:

     import random weighted_choice = lambda s : random.choice(sum(([v]*wt for v,wt in s),[])) 

    Это работает?

     # define choices and relative weights choices = [("WHITE",90), ("RED",8), ("GREEN",2)] # initialize tally dict tally = dict.fromkeys(choices, 0) # tally up 1000 weighted choices for i in xrange(1000): tally[weighted_choice(choices)] += 1 print tally.items() 

    Печать:

     [('WHITE', 904), ('GREEN', 22), ('RED', 74)] 

    Предполагается, что все веса являются целыми числами. Им не нужно добавлять до 100, я просто сделал это, чтобы облегчить интерпретацию результатов теста. (Если веса являются числами с плавающей запятой, умножьте их на 10 раз, пока все веса> = 1.)

     weights = [.6, .2, .001, .199] while any(w < 1.0 for w in weights): weights = [w*10 for w in weights] weights = map(int, weights) 

    Если у вас есть взвешенный словарь вместо списка, вы можете написать это

     items = { "a": 10, "b": 5, "c": 1 } random.choice([k for k in items for dummy in range(items[k])]) 

    Обратите внимание, что [k for k in items for dummy in range(items[k])] создает этот список ['a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'c', 'b', 'b', 'b', 'b', 'b']

    Вот версия, которая включена в стандартную библиотеку для Python 3.6:

     import itertools as _itertools import bisect as _bisect class Random36(random.Random): "Show the code included in the Python 3.6 version of the Random class" def choices(self, population, weights=None, *, cum_weights=None, k=1): """Return ak sized list of population elements chosen with replacement. If the relative weights or cumulative weights are not specified, the selections are made with equal probability. """ random = self.random if cum_weights is None: if weights is None: _int = int total = len(population) return [population[_int(random() * total)] for i in range(k)] cum_weights = list(_itertools.accumulate(weights)) elif weights is not None: raise TypeError('Cannot specify both weights and cumulative weights') if len(cum_weights) != len(population): raise ValueError('The number of weights does not match the population') bisect = _bisect.bisect total = cum_weights[-1] return [population[bisect(cum_weights, random() * total)] for i in range(k)] 

    Источник: https://hg.python.org/cpython/file/tip/Lib/random.py#l340

    Начиная с Python v3.6 , random.choices можно использовать для возврата list элементов заданного размера из данной группы с дополнительными весами.

    random.choices(population, weights=None, *, cum_weights=None, k=1)

    • население : list содержащий уникальные наблюдения. (Если пусто, вызывает IndexError )

    • вес : более точно относительные веса, необходимые для выбора.

    • cum_weights : совокупный вес, необходимый для выбора.

    • k : размер ( len ) list должен быть выведен. (По умолчанию len()=1 )


    Немного оговорок:

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

    В отличие от np.random.choice который может принимать только вероятности в виде весов и также должен обеспечивать суммирование индивидуальных вероятностей до 1 критерия, здесь нет таких правил. Пока они относятся к числовым типам ( int/float/fraction except Decimal type), они все равно будут выполняться.

     >>> import random # weights being integers >>> random.choices(["white", "green", "red"], [12, 12, 4], k=10) ['green', 'red', 'green', 'white', 'white', 'white', 'green', 'white', 'red', 'white'] # weights being floats >>> random.choices(["white", "green", "red"], [.12, .12, .04], k=10) ['white', 'white', 'green', 'green', 'red', 'red', 'white', 'green', 'white', 'green'] # weights being fractions >>> random.choices(["white", "green", "red"], [12/100, 12/100, 4/100], k=10) ['green', 'green', 'white', 'red', 'green', 'red', 'white', 'green', 'green', 'green'] 

    2) Если не указаны ни веса, ни cum_weights , выбор производится с равной вероятностью. Если задана последовательность весов , она должна быть такой же длины, как и последовательность популяции .

    Задание как весов, так и cum_weights вызывает TypeError .

     >>> random.choices(["white", "green", "red"], k=10) ['white', 'white', 'green', 'red', 'red', 'red', 'white', 'white', 'white', 'green'] 

    3) cum_weights обычно являются результатом itertools.accumulate функции, которые действительно удобны в таких ситуациях.

    Из связанной документации:

    Внутренне относительные веса преобразуются в кумулятивные веса перед выбором, поэтому поставка кумулятивных весов экономит работу.

    Таким образом, либо поставка weights=[12, 12, 4] либо cum_weights=[12, 24, 28] для нашего надуманного случая дает один и тот же результат, а последний, кажется, более быстрый / эффективный.

    Я бы потребовал сумму выборов 1, но это все равно работает

     def weightedChoice(choices): # Safety check, you can remove it for c,w in choices: assert w >= 0 tmp = random.uniform(0, sum(c for c,w in choices)) for choice,weight in choices: if tmp < weight: return choice else: tmp -= weight raise ValueError('Negative values in input') 

    Общее решение:

     import random def weighted_choice(choices, weights): total = sum(weights) treshold = random.uniform(0, total) for k, weight in enumerate(weights): total -= weight if total < treshold: return choices[k] 
     import numpy as np w=np.array([ 0.4, 0.8, 1.6, 0.8, 0.4]) np.random.choice(w, p=w/sum(w)) 

    Возможно, я слишком поздно внес что-либо полезное, но вот простой, короткий и очень эффективный фрагмент:

     def choose_index(probabilies): cmf = probabilies[0] choice = random.random() for k in xrange(len(probabilies)): if choice <= cmf: return k else: cmf += probabilies[k+1] 

    Не нужно сортировать свои вероятности или создавать вектор с вашим cmf, и он прекращается, как только он находит свой выбор. Память: O (1), время: O (N), со средним временем работы ~ N / 2.

    Если у вас есть веса, просто добавьте одну строку:

     def choose_index(weights): probabilities = weights / sum(weights) cmf = probabilies[0] choice = random.random() for k in xrange(len(probabilies)): if choice <= cmf: return k else: cmf += probabilies[k+1] 

    Если ваш список взвешенных вариантов относительно статичен и вам нужна частая выборка, вы можете сделать один шаг предварительной обработки O (N), а затем сделать выбор в O (1), используя функции в этом связанном ответе .

     # run only when `choices` changes. preprocessed_data = prep(weight for _,weight in choices) # O(1) selection value = choices[sample(preprocessed_data)][0] 

    Я посмотрел на другую тему и придумал эту вариацию в моем стиле кодирования, это возвращает индекс выбора для целей подсчета голосов, но просто вернуть строку (прокомментированная альтернатива возврата):

     import random import bisect try: range = xrange except: pass def weighted_choice(choices): total, cumulative = 0, [] for c,w in choices: total += w cumulative.append((total, c)) r = random.uniform(0, total) # return index return bisect.bisect(cumulative, (r,)) # return item string #return choices[bisect.bisect(cumulative, (r,))][0] # define choices and relative weights choices = [("WHITE",90), ("RED",8), ("GREEN",2)] tally = [0 for item in choices] n = 100000 # tally up n weighted choices for i in range(n): tally[weighted_choice(choices)] += 1 print([t/sum(tally)*100 for t in tally]) 

    Вот еще одна версия weighted_choice, которая использует numpy. Перейдите в вектор весов, и он вернет массив из 0, содержащий 1, указывающий, какой бункер выбран. В коде по умолчанию используется только однократная ничья, но вы можете передать количество ничьих, которые будут сделаны, и будет возвращено количество отсчетов на извлеченный бит.

    Если вектор весов не суммируется с 1, он будет нормализован так, чтобы он выполнялся.

     import numpy as np def weighted_choice(weights, n=1): if np.sum(weights)!=1: weights = weights/np.sum(weights) draws = np.random.random_sample(size=n) weights = np.cumsum(weights) weights = np.insert(weights,0,0.0) counts = np.histogram(draws, bins=weights) return(counts[0]) 
    Python - лучший язык программирования в мире.