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.
Vous devez vous connecter pour publier un commentaire.
Vous êtes à la recherche pour le alias méthode qui fournit un O(1) méthode pour générer un fixe discret distribution de probabilité (en supposant que vous pouvez accéder à des entrées dans un tableau de longueur n en temps constant) avec un temps O(n) set-up. Vous pouvez le trouver documenté dans le chapitre 3 (PDF) de "Non-Uniforme Aléatoire De La Variable Aléatoire De La Génération" par Luc Devroye.
L'idée est de prendre votre tableau de probabilités pk et produire trois nouveaux n-élément tableaux, qk,k et bk. Chaque qk est une probabilité comprise entre 0 et 1, et chaquek et bk est un nombre entier compris entre 1 et n.
Nous générer des nombres aléatoires entre 1 et n, par la génération de deux nombres aléatoires, r et s, entre 0 et 1. Soit i = plancher(r*N)+1. Si qi < s, puis retour ai else return bi. Le travail dans l'alias de la méthode est de trouver comment produire qk,k et bk.
n
et pour un nombre choisi de nombres aléatoires pour générer due à la constante de facteurs impliqués dans la mise en œuvre des algorithmes.Utilisation d'un équilibre binaire un arbre de recherche (ou de recherche binaire dans un tableau) et obtenir O(log n) la complexité. Avoir un nœud pour chaque dé de résultat et d'avoir les clés de l'intervalle qui va déclencher ce résultat.
La bonne chose à propos de cette solution est qu'elle est très simple à mettre en œuvre, mais a encore une bonne complexité.
Je pense à la granulation de votre table.
Au lieu d'avoir un tableau avec les cumulatif pour chaque valeur de dé, vous pouvez créer un tableau d'entiers de longueur xN, où x est de préférence un nombre élevé pour augmenter la précision de la probabilité.
Remplir ce tableau à l'aide de l'index (normalisée par xN) comme la valeur cumulative et, dans chaque "machine à sous" dans le tableau, de stocker les dés si cet indice vient.
Je pourrais peut-être plus facile d'expliquer avec un exemple:
À l'aide de trois dés: P(1) = 0.2, P(2) = 0.5, P(3) = 0.3
Créer un tableau, dans ce cas, je vais choisir un simple longueur, disons, 10. (qui est, x = 3.33333)
Ensuite, pour obtenir la probabilité, juste aléatoire un nombre entre 0 et 10, il vous suffit d'accéder à cet indice.
Cette méthode risquons de perdre de la précision, mais augmentation de x et de la précision sera suffisant.