Структура данных для загруженных кубиков?

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

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

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

EDIT : На основе ответов на этот вопрос я написал статью, описывающую многие подходы к этой проблеме , а также их анализ. Похоже, что реализация Vose метода псевдонима дает Θ (n) время предварительной обработки и O (1) раз за бросок кубика, что действительно впечатляет. Надеюсь, это полезное дополнение к информации, содержащейся в ответах!

3 Solutions collect form web for “Структура данных для загруженных кубиков?”

Вы ищете метод псевдонима, который предоставляет метод 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 = пол (r * N) +1. Если q i i else return 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 и точности будет достаточно.

Давайте будем гением компьютера.