Генератор псевдослучайных чисел с зависимой вероятностью вывода нужных чисел?
Есть задача:
На основе каких-нибудь готовых средств или функций (например, rand) нужно сделать функцию, которая будет возвращать по заданному диапазону (или готовому набору каких-то чисел) псевдослучайные числа, причем не равномерно, а по какой-то задаваемой зависимости. В качестве базовой можно взять следующую зависимость: возвращать чаще большие значения. При этом возникает резонный вопрос, насколько чаще. Тут также предлагается какой-нибудь любой задаваемый вариант, например, во столько раз чаще, насколько порядковый номер данного элемента в массиве больше.
Пример:
Массив m = [1, 3, 7, 19]. Мы вызываем нашу функцию getMyRand() передавая в нее массив (или диапазон, если нет массива). В результате получаем какие-то такие значения (номер вызова функции — возвращенное значение):
1 — 19
2 — 7
3 — 19
4 — 19
5 — 3
6 — 19
7 — 7
8 — 1
9 — 19
10 — 7
11 — 19
12 — 7
13 — 3
14 — 19
15 — 19
и т.д.
Если есть какие мысли, как подступиться к такой функции, хотелось бы услышать и пообсуждать.
Чем она может быть интересна? Например, написать бота, который будет посещать сайты и симулировать просмотры страниц близко к поведению человека.
Элементарно Ватсон, вам нужна функция, которая будет давать случайные числа с заданным распределением.
Например:
возвращать чаще большие значения
— это экспоненциальная, или показательная функция. Я как-то занимался данным вопросом. Вам нужно сделать обратное преобразование функции распределения и просто подставлять туда свои значения и на выходе иметь с нужным распределением.
Стандартного распределения вполне хватило. Остальное получается путем их различных комбинаций. А цепь событий может быть любая, для нас интересны поведенческие модели человека, что он делает чаще, что реже, соответственно робот должен делать также.
И количество итераций увеличите до десятков тысяч. Кстати, для выбора количества точек на распределение я использую следующую формулу (в какой-то диссертации подсмотрел)
Я когда-то делал генератор псч с произвольным распределением через хэш-функцию. Алгоритм лобовой, на математическую и техническую красоту не претендует, но все равно я его опишу, вдруг кому-то пригодится.
— Нам нужен генератор псч, скажем от 0 до 99 с варьируемой вероятностю выпадения чисел.
— Заводим массив из 10000 элементов. Все числа заносим в массив по 100 раз.
— Выбирая из массива число со случайным (через обычный гпсч) индексом от 0 до 9999, мы получим число от 0 до 99 с равной вероятностью.
— Для уменьшения вероятности выпадения числа нужно уменьшить количество этих чисел в массиве. Например, если число «8» будет входить в массив не 100, а 50 раз — то его вероятность выпадения будет вдвое ниже, чем остальных.
— Для увеличения вероятности выпадения числа расширяем массив и добавляем ещё таких чисел.
Таким образом, можно построить почти любую функцию распределения (разумеется, с ограничениями на коэффициенты вероятности выпадения чисел). Плавность растройки такого генератора напрямую зависит от размера массива.
Да, решение оправдывается для некоторых случаев, но как уже отмечено, не подходит для всех действительных чисел, только натуральные. А если диапазон большой, например, от 1 до 1 млн, то массив слишком велик и необходимы большие вычислительные ресурсы.
Полностью согласен, решение подходит для ограниченного круга задач, где требуется произвольное распределение, число вариантов выхода дискретно и невелико, а настройки вероятностей не слишком плавные.
Для варианта конечной дискретной последовательности (как в Вашем случае) задача решается достаточно просто вариацией метода Монте-Карло.
Допустим у нас есть массив A натуральных чисел от 0 до n (0, 1, ..., n — 1) и для каждого из этих чисел задана вероятность его генерации p(a_i) (естественно, сумма всех вероятностей равна 1). Идея метода: разделить отрезок [0;1) на n отрезков, длина каждого из которых равна вероятности появления соответствующего числа из массива А. Далее, уже стандартным генератором ПСЧ выбираем число в диапазоне [0;1) и проверяем в какой из отрезков оно попало. Соответствующий данному отрезку элемент исходного массива возвращаем в качестве результата работы нашего генератора.
Реализацию алгоритма оставим читателю в качестве домашнего задания :)
В предложенном выше решении для того, чтобы увеличить скорость генерации чисел, пожертвовали памятью, причем конкретно так, не скупясь, на порядок.
В моей версии размер массива ровно равен требуемой дискретности (собственно, можно обойтись только массивом вероятностей, хотя это несколько (на одну операцию сложения) снизит скорость работы). Да, в моем варианте скорость генерации ниже (по причине необходимости просматривать массив вероятностей сначала до, в худшем случае, конца), но, для задач, озвученных ТС — имхо, некритично.
Мое тупое, но рабочее решение описано тут habrahabr.ru/post/194598/ — доработанную версию использовал в последнем проекте. Генерирует все по моим правилам, быстро и четко.
Простой
Простой
Средний
Простой
