加载的骰子的数据结构？

Question

假设我有一个n面加载的模具，其中每边k 滚动时都有几率p _k上升。我很好奇是否有一个好的算法可以静态地存储此信息（例如，针对一组固定的概率），以便可以有效地模拟骰子的随机滚动。

目前，我有一个O（lg n）解决方案。这个想法是存储一张表，存储所有k的前k个边的累积概率，它们在[0，1）范围内生成一个随机实数，并对该表执行二进制搜索以获取最大的索引，该索引的累积值不大于所选值。我宁愿喜欢这种解决方案，但运行时没有考虑这些可能性似乎很奇怪。特别地，在极端情况下，一侧总是出现或值均匀分布，尽管我的解决方案仍将采取对数步的许多方法，但可以通过朴素的方法在O（1）中生成滚动结果。

有人对运行时以某种“自适应”方式解决此问题有任何建议吗？

编辑：基于对这个问题的回答，我写了一篇文章，描述了解决这个问题的许多方法以及它们的分析。看起来Vose对别名方法的实现为每个模具辊提供了Θ（n）预处理时间和O（1）时间，这确实令人印象深刻。希望这是对答案中包含的信息的有用补充！

Answer 1

使用平衡的二叉搜索树（或数组中的二叉搜索）并获得O（log n）复杂度。每个骰子结果只有一个节点，并且键是触发该结果的间隔。function get_result(node, seed):&nbsp; &nbsp; if seed < node.interval.start:&nbsp; &nbsp; &nbsp; &nbsp; return get_result(node.left_child, seed)&nbsp; &nbsp; else if seed < node.interval.end:&nbsp; &nbsp; &nbsp; &nbsp; // start <= seed < end&nbsp; &nbsp; &nbsp; &nbsp; return node.result&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; return get_result(node.right_child, seed)该解决方案的优点是实现起来非常简单，但是仍然具有很好的复杂性。

Answer 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且精度就足够了。