Структура данных для загруженных игральных костей?

Предположим, что у меня есть n-сторонний загруженный кубик, где каждая сторона k имеет некоторую вероятность p _K приходить, когда я раскатать. Мне любопытно, есть ли хороший алгоритм для статического хранения этой информации (то есть для фиксированного набора вероятностей), чтобы я мог эффективно моделировать случайный бросок кубика.

В настоящее время у меня есть решение этой проблемы за O (lg n). Идея состоит в том, чтобы сохранить таблицу кумулятивной вероятности первых k сторон для всех k, чтобы они генерировали случайное действительное число в диапазоне [0, 1) и выполняли двоичный поиск по таблице, чтобы получить наибольший индекс, совокупный значение не больше, чем выбранное значение. Мне это решение нравится, но кажется странным, что среда выполнения не принимает во внимание вероятности. В частности, в экстремальных случаях, когда одна сторона всегда подходит или значения равномерно распределены, можно сгенерировать результат броска в O (1), используя наивный подход, хотя мое решение все равно будет принимать логарифмически много шагов.

Есть ли у кого-нибудь предложения, как решить эту проблему таким образом, чтобы это было как-то «адаптивно» во время выполнения?

РЕДАКТИРОВАТЬ : Основываясь на ответах на этот вопрос, я написал статью, в которой описаны многие подходы к этой проблеме , а также их анализ. Похоже, что реализация Vose метода псевдонима дает Θ (n) времени предварительной обработки и O (1) раз на бросок кубика, что действительно впечатляет. Надеюсь, это будет полезным дополнением к информации, содержащейся в ответах!

Вы ищете метод псевдонима, который предоставляет метод O (1) для генерации фиксированного дискретного распределения вероятностей (при условии, что вы можете получить доступ к записям в массиве длины n за постоянное время) с одноразовой настройкой O (n) , Вы можете найти это задокументированное в главе 3 (PDF) книги Люка Девроя «Генерация неоднородной случайной величины» .

Идея состоит в том, чтобы взять ваш массив вероятностей p _k и создать три новых n-элементных массива: q _k , a _k и b _k . Каждое q _k представляет собой вероятность от 0 до 1, а каждое a _k и b _k является целым числом от 1 до n.

Мы генерируем случайные числа от 1 до n, генерируя два случайных числа, r и s, от 0 до 1. Пусть i = floor (r * N) +1. Если q _i <s, тогда верните a _i, иначе верните b _i . Работа в методе псевдонима состоит в том, чтобы выяснить, как произвести q _k , a _k и b _k .

Используйте сбалансированное двоичное дерево поиска (или двоичный поиск в массиве) и получите сложность O (log n). Имейте по одному узлу для каждого результата кубика, а ключи должны быть интервалом, который вызовет этот результат.

function get_result(node, seed):
    if seed < node.interval.start:
        return get_result(node.left_child, seed)
    else if seed < node.interval.end:
        // start <= seed < end
        return node.result
    else:
        return get_result(node.right_child, seed)

Преимущество этого решения в том, что его очень просто реализовать, но при этом он имеет хорошую сложность.

Я думаю о гранулировании вашего стола.

Вместо того, чтобы иметь таблицу с кумулятивным значением для каждого значения кубика, вы можете создать целочисленный массив длиной xN, где x в идеале является большим числом, чтобы повысить точность вероятности.

Заполните этот массив, используя индекс (нормализованный xN) в качестве кумулятивного значения, и в каждом «слоте» в массиве сохраните предполагаемый бросок кости, если этот индекс появится.

Может быть, я мог бы проще объяснить на примере:

Используя три кубика: P (1) = 0,2, P (2) = 0,5, P (3) = 0,3

Создайте массив, в этом случае я выберу простую длину, скажем 10. (то есть x = 3,33333).

arr[0] = 1,
arr[1] = 1,
arr[2] = 2,
arr[3] = 2,
arr[4] = 2,
arr[5] = 2,
arr[6] = 2,
arr[7] = 3,
arr[8] = 3,
arr[9] = 3

Затем, чтобы получить вероятность, просто рандомизируйте число от 0 до 10 и просто получите доступ к этому индексу.

Этот метод может потерять точность, но увеличения x и точности будет достаточно.

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

Один из простейших способов выбрать целое число с помощью настраиваемой весовой функции f(x)- это метод отклонения выборки . Ниже предполагается, что максимально возможное значение fравно max. Временная сложность выборки отбраковки в среднем постоянна, но сильно зависит от формы распределения и, в худшем случае, работает вечно. Чтобы выбрать целое число в [1, k] с помощью выборки отклонения:

1. Выберите равномерное случайное целое число iв [1,k ].
2. С вероятностью f(i)/maxвернусь i. В противном случае перейдите к шагу 1.

Другие алгоритмы имеют среднее время выборки, которое не так сильно зависит от распределения (обычно либо постоянное, либо логарифмическое), но часто требует, чтобы вы предварительно вычислили веса на этапе настройки и сохранили их в структуре данных. Некоторые из них также экономичны с точки зрения количества используемых в среднем случайных битов. Многие из этих алгоритмов были введены после 2011 года, и они включают:

• сжатая структура данных Брингмана – Ларсена («Краткая выборка из дискретных распределений», 2012),
• Многоуровневый поиск Юньпэн Тан («Эмпирическое исследование методов случайной выборки для изменения дискретных распределений», 2019) и
• Ролик для игры в кости с быстрой загрузкой (2020).

Другие алгоритмы включают метод псевдонима (уже упомянутый в вашей статье), алгоритм Кнута – Яо, структуру данных MVN и многое другое. См. Мой раздел « Замечание об алгоритмах взвешенного выбора » для обзора.