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

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

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

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

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

Ответ 1

Вы ищете метод alias, который предоставляет метод O (1) для создания фиксированной дискретной вероятности (предполагая, что вы можете обращаться к записям в массиве длиной n в постоянное время) с одноразовой настройкой O (n). Вы можете найти его в глава 3 (PDF) "Non-Uniform Random Variate Generation" от Luc Devroye.

Идея состоит в том, чтобы взять ваш массив вероятностей 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. Пусть я = пол (r * N) +1. Если q _i < затем верните _i else return b _i. Работа в методе псевдонимов заключается в том, чтобы выяснить, как создать q _k, a _k и b _k.

Ответ 2

Я думаю о гранулировании таблицы.

Вместо того, чтобы иметь таблицу с суммарным значением для каждого значения матрицы, вы можете создать целочисленный массив длины 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 и точности будет достаточно.

Ответ 3

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

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)

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