Structure de données pour les dés pipés?

Supposons que j'ai un n-sided chargé de mourir où chaque côté k a une certaine probabilité pk de venir quand je le rouler. Je suis curieux de savoir si il est bon algorithme pour le stockage de cette information de manière statique (c'est à dire pour un ensemble fixe de probabilités) afin que je puisse efficacement simuler un jet de hasard du dé.

Actuellement, j'ai un O(lg n) solution pour ce problème. L'idée est de stocker un tableau de la probabilité cumulée de la première k côtés pour tout k, afin de générer un nombre réel aléatoire dans l'intervalle [0, 1) et d'effectuer une recherche binaire sur la table pour obtenir le plus grand indice dont la valeur cumulative est inférieure à la valeur choisie. J'aime assez cette solution, mais il semble étrange que l'exécution ne prend pas les probabilités en compte. En particulier, dans les deux extrémités des cas, d'un côté, toujours à venir ou les valeurs étant uniformément répartie, il est possible de générer le résultat de la mise en O(1) à l'aide d'une approche naïve, bien que ma solution va encore prendre logarithmicallh de nombreuses étapes.

Quelqu'un aurait-il des suggestions sur la façon de résoudre ce problème d'une manière qui est en quelque sorte "adaptative" dans son exécution?

MODIFIER: sur la Base des réponses à cette question, j'ai écrit un article décrivant de nombreuses approches à ce problème, ainsi que leurs analyses. Il ressemble à Vose de la mise en œuvre de l'alias méthode donne Θ(n) temps de prétraitement et de O(1) fois par jet de dé, qui est vraiment impressionnante. J'espère que c'est un complément utile à l'information contenue dans les réponses!

  • Il est raisonnable qu'il existe un O(1) solution pour chaque cas spécifique.