加载骰子的数据结构？
假设我有一个n边加载的模子，当我滚动它时，每个边k有一些概率pk 。 我很好奇，如果有一个很好的algorithm来静态存储这个信息（即对于一组固定的概率），这样我就可以高效地模拟一个随机掷骰子。
目前，我有一个O（LG）的解决scheme，这个问题。 这个想法是为所有k存储一个前k个边的累积概率表，它们在[0,1）范围内产生一个随机实数，然后在表上进行二分search，得到最大的累积索引值不大于选定的值。 我更喜欢这个解决scheme，但运行时不考虑概率似乎很奇怪。 特别是在极端情况下，一方面总是出现或者价值是均匀分布的，可能使用一种简单的方法在O（1）中生成滚动的结果，尽pipe我的解决scheme仍然需要对数很多的步骤。
有没有人有任何build议，如何解决这个问题的方式是在某种程度上“适应”在运行时？
编辑 ：基于这个问题的答案，我写了一篇文章，描述了这个问题的许多方法 ，以及他们的分析。 它看起来像Vose的别名方法的实施给予Θ（n）预处理时间和O（1）时间每个die roll，这真是令人印象深刻。 希望这是对答案中包含的信息的有益补充！
您正在寻找别名方法 ，该方法提供了一个O（1）方法来生成一个固定的离散概率分布（假设您可以使用一次性O（n）设置访问长度为n的数组中的条目） 。 您可以在Luc Devroye的“非均匀随机variables生成”的第3章（PDF）中find它。
这个想法是把你的概率pk，并产生三个新的n元素arrays，q k ，a k和b k 。 每个q k是0到1之间的概率，并且每个a k和b k是1和n之间的整数。
我们通过在0和1之间生成两个随机数r和s来生成1和n之间的随机数。令i = floor（r * N）+1。 如果q 我 <s然后返回一个我还是返回b 我 。 在别名方法中的工作是弄清楚如何产生q k ，a k和b k 。
使用平衡二叉search树（或在数组中进行二分search）并获得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)
这个解决scheme的好处是非常简单，但仍然具有很好的复杂性。
我正在考虑把你的桌子造粒。
您可以创build一个长度为xN的整数数组，而不必为每个模值添加一个表，其中x理想情况下是一个高数，以提高概率的准确性。
使用索引（由xN标准化）作为累积值填充此数组，并在数组中的每个“插槽”中存储可能的骰子卷（如果此索引出现）。
也许我可以用一个例子来解释一下：
使用三个骰子：P（1）= 0.2，P（2）= 0.5，P（3）= 0.3
创build一个数组，在这种情况下，我会select一个简单的长度，比如说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和准确性就足够了。
