Имитация "Колеса фортуны" (метод симуляции удара или мисс Монте-Карло)

Question

Я пытаюсь создать рандомизатор, который будет использовать Монте-Карло Хит или Мисс Симуляция.

У меня есть пара ключ-значение, которая представляет идентификатор и значение вероятности:

ID - Value
2  - 0.37
1 - 0.35
4 - 0.14
3 - 0.12

Когда вы добавите все эти значения, вы получите в общей сложности 1,0.

Вы можете представить эти значения как общую площадь "среза" на "колесе" (например, ID 2 занимает 37% колеса, в то время как ID 3 занимает только 12% колеса). При преобразовании в «диапазон» это будет выглядеть так:

ID - Value - Range
2  - 0.37 - 0 to 37
1 - 0.35 - 37 to 72
4 - 0.14 - 72 to 86
3 - 0.12- 86 to 100

Теперь я использую Random.NextDouble () для генерации случайного значения в диапазоне от 0,0 до 1,0. Это случайное значение будет рассматриваться как «вращение» на колесе. Скажем, рандомизатор возвращает 0.35, тогда будет выбран идентификатор 2.

Каков наилучший способ реализовать это, учитывая, что у меня есть массив значений типа double?

Answer 1

Простейшие решения часто являются лучшими, если ваш диапазон от 0 до 100 (или другое небольшое число), вы можете выделить int[] и использовать таблицу диапазонов, которую вы создали, чтобы заполнить идентификатор на соответствующий индекс, ваш «бросок» будет выглядеть так:

int randomID = rangesToIDs[random.nextInt(rangesToIDs.length)];

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

Answer 2

Предположим, ваши исходные данные представлены в виде массива D [n], где D [i] = (id, p) и сумма (D [i] .p для i = 0..n-1) == 1 .

Создайте второй массив P [n] так, чтобы P [i] = (q, id): P [i] = (сумма (D [j] .p для j в 0..i), D [j] ] .id) - то есть преобразовать индивидуальную вероятность каждого среза i в совокупную вероятность всех срезов, предшествующих i (включительно). Отметим, что по определению этот массив P упорядочен по полю q (т.е. по кумулятивной вероятности).

Теперь вы можете использовать двоичный поиск , чтобы найти срез, выбранный случайным числом r (0 <= r <= 1): </p>

найти старшее i такое, что P [i] .q <= r; тогда P [i] .id - ваш срез. </p>

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

Answer 3

boundaries = [37, 72, 86, 100]
num = 100 * random
for i in boundaries:
  if num < i then return i

Answer 4

Как пишет jk, отсортированный словарь должен быть в порядке.

допустим, у вас есть словарь такой:

0,37 2
0,72 1
0,86 4
1,00 3

Вы бросаете хх = 0,66 .. Итерация по словарю, начиная с наименьшего числа (это 0,37) если хх

Или другое решение, которое мне приходит в голову, это Список пользовательских объектов, содержащих нижнюю и верхнюю границу и значение. Затем вы перебираете список и проверяете, находится ли выпавший номер в диапазоне верхних и нижних границ.

Answer 5

отсортированная карта / словарь с «Value» в качестве ключа и «ID» в качестве значения позволит вам быстро найти верхнюю границу диапазона, в котором вы находитесь, а затем найти идентификатор для этого диапазона

Если ваш словарь позволяет это сделать, лучше найти верхнюю границу двоичного поиска, чем целое по всему словарю