gcc по умолчанию не строит никаких функций при компиляции без оптимизации. Я не знаю о visual studio - deft_code
blockquote>Я проверил это для Visual Studio 9 (15.00.30729.01), компилировав / FAcs и посмотрев на код сборки: компилятор произвел вызовы функции-члены без оптимизации включены в режиме отладки. Даже если функция отмечена __forceinline, не создается встроенный код времени выполнения.
Начиная с версии 1.7.0, NumPy имеет функцию choice
, которая поддерживает распределения вероятностей.
from numpy.random import choice
draw = choice(list_of_candidates, number_of_items_to_pick, p=probability_distribution)
Обратите внимание, что probability_distribution
представляет собой последовательность в том же порядке из list_of_candidates
. Вы также можете использовать ключевое слово replace=False
, чтобы изменить поведение так, чтобы нарисованные элементы не были заменены.
Возможно, я слишком поздно внес что-либо полезное, но вот простой, короткий и очень эффективный фрагмент:
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), используя функции в , связанные с этим answer .
# run only when `choices` changes.
preprocessed_data = prep(weight for _,weight in choices)
# O(1) selection
value = choices[sample(preprocessed_data)][0]
0.0 <= x < total
. 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'
Если вам нужно сделать несколько вариантов, разделите их на две функции: одну для построения кумулятивных весов и другую для деления пополам на случайную точку.
Общее решение:
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]
Если у вас есть взвешенный словарь вместо списка, вы можете записать это
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']
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"
Вот еще одна версия 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 v3.6
, random.choices
можно было бы использовать для возврата list
элементов заданного размера из данной популяции с дополнительными весами.
blockquote>
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
, кроме типаDecimal
), они все равно будут выполняться.>>> 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
, которые действительно удобны в таких ситуациях.Из связанной документации:
Внутренне относительные веса преобразуются в кумулятивные веса перед выбором, поэтому загрузка кумулятивных весов экономит работу.
blockquote>Таким образом, либо поставка
weights=[12, 12, 4]
, либоcum_weights=[12, 24, 28]
для нашего надуманного случая дает один и тот же результат, а последний, по-видимому, работает быстрее / эффективнее.
Грубый, но может быть достаточным:
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)
Один из способов - рандомизировать по сумме всех весов, а затем использовать значения в качестве предельных точек для каждого var. Вот грубая реализация как генератор.
def rand_weighted(weights):
"""
Generator which uses the weights to generate a
weighted random values
"""
sum_weights = sum(weights.values())
cum_weights = {}
current_weight = 0
for key, value in sorted(weights.iteritems()):
current_weight += value
cum_weights[key] = current_weight
while True:
sel = int(random.uniform(0, 1) * sum_weights)
for key, value in sorted(cum_weights.iteritems()):
if sel < value:
break
yield key
Я бы потребовал сумму выборов 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')
Если вы не против использования 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)
Вот версия, которая включена в стандартную библиотеку для 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 a k 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
Я посмотрел на другую тему и придумал эту вариацию в моем стиле кодирования, это возвращает индекс выбора для целей подсчета голосов, но просто вернуть строку (прокомментированную альтернативу возврата):
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])
Это зависит от того, сколько раз вы хотите пробовать распространение.
Предположим, вы хотите пробовать распределение K раз. Тогда временная сложность с использованием np.random.choice()
каждый раз равна O(K(n + log(n)))
, когда n
- количество элементов в распределении.
В моем случае мне понадобилось пробовать одно и то же распределение несколько раз порядка 10 ^ 3, где n имеет порядок 10 ^ 6. Я использовал приведенный ниже код, который предварительно вычисляет кумулятивное распределение и отображает его в O(log(n))
. Общая временная сложность - O(n+K*log(n))
.
import numpy as np
n,k = 10**6,10**3
# Create dummy distribution
a = np.array([i+1 for i in range(n)])
p = np.array([1.0/n]*n)
cfd = p.cumsum()
for _ in range(k):
x = np.random.uniform()
idx = cfd.searchsorted(x, side='right')
sampled_element = a[idx]
Поскольку 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]: random.choices(
...: population=[['a','b'], ['b','a'], ['c','b']],
...: weights=[0.2, 0.2, 0.6],
...: k=10
...: )
Out[2]:
[['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 .
UPDATE: As @roganjosh , random.choices
не может возвращать значения без замены, как упоминалось в docs :
Вернуть a
k
(g15) blockquote>И блестящий ответ @ ronan-paixão гласит, что
numpy.choice
имеет аргументreplace
, который управляет этим поведением.
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))