Вот некоторый псевдокод:
count = 0
for every item in a list
1/20 chance to add one to count
Это более или менее мой текущий код, но в этом списке могут быть сотни тысяч элементов; поэтому он быстро становится неэффективным. (разве это не называется 0(n) или как-то так?)
Есть ли способ сжать это в одно уравнение?
Давайте посмотрим на свойства описанной вами случайной величины. Цитата из Википедии:
Биномиальное распределение с параметрами n и p — это дискретное распределение вероятностей числа успехов в последовательности из n независимых экспериментов «да/нет», каждый из которых дает успех с вероятностью p.
Пусть N будет количеством элементов в списке, а C будет случайной величиной, представляющей count, которую вы получаете из своего псевдокода. C будет следовать биномиальному распределению вероятностей (как показано на изображении ниже) с p = 1/20:
Оставшаяся проблема заключается в том, как эффективно опросить случайную величину с указанным распределением вероятностей. Существует ряд библиотек, которые позволяют вам делать выборки из случайных величин с заданным PDF. Мне никогда не приходилось реализовывать это самому, поэтому я точно не знаю деталей, но многие из них имеют открытый исходный код, и вы можете сами ознакомиться с реализацией.
Вот как можно рассчитать count с помощью библиотеки numpy в Python:
n, p = 10, 0.05 # 10 trials, probability of success is 0.05
count = np.random.binomial(n, p) # draw a single sample
По-видимому, ОП просил более эффективный способ генерации случайных чисел с тем же распределением, которое это даст. Хотя вопрос заключался в том, как выполнить ту же операцию, что и в цикле, но в виде одного вкладыша (и желательно без временного списка, который существует только для повторения).
Если вы сэмплируете генератор случайных чисел n раз, в лучшем случае он будет иметь время выполнения O (n), независимо от того, как выглядит код.
В некоторых интерпретируемых языках использование более компактного синтаксиса может заметно повлиять на постоянные факторы времени выполнения. Другие факторы могут повлиять на время выполнения, например, будете ли вы сохранять все случайные значения и затем их обрабатывать или обрабатывать на лету без временного хранения.
Ничто из этого не позволит вам избежать линейного увеличения времени выполнения с n.
