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

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

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

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

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