加载骰子的数据结构？

Question

假设我有一个n侧加载的模具,当我滚动它时,每个侧面k都有一些概率p _k.我很好奇是否存在静态存储此信息的良好算法(即,对于一组固定的概率),以便我可以有效地模拟模具的随机滚动.

目前,我有一个针对此问题的O(lg n)解决方案.想法是存储所有k的前k个边的累积概率的表,它们生成范围[0,1)中的随机实数并且对表执行二元搜索以获得其累积的最大索引值不大于所选值.我更喜欢这个解决方案,但运行时没有考虑概率似乎很奇怪.特别是,在一方总是出现或值均匀分布的极端情况下,可以使用朴素的方法在O(1)中生成滚动的结果,尽管我的解决方案仍然需要采用多个步骤的对数.

有没有人对如何以某种方式在运行时"自适应"的方式解决这个问题有任何建议？

编辑:基于这个问题的答案,我写了一篇文章,描述了这个问题的许多方法,以及他们的分析.看起来Vose的别名方法的实现给出了Θ(n)预处理时间和每次掷骰的O(1)时间,这确实令人印象深刻.希望这是对答案中包含的信息的有用补充!

Answer 1

您正在寻找别名方法,该方法提供O(1)方法来生成固定的离散概率分布(假设您可以在恒定时间内访问长度为n的数组中的条目)并使用一次性O(n)设置.您可以在Luc Devroye 的"非均匀随机变量生成"的第3章(PDF)中找到它.

我们的想法是获取你的概率数组p _k并产生三个新的n元素数组q _k,a _k和b _k.每个q _k是0和1之间的概率,并且每个_k和b _k是1和n之间的整数.

我们通过在0和1之间生成两个随机数r和s来生成1到n之间的随机数.设i = floor(r*N)+1.如果q _i <s然后返回_i,则返回b _i.别名方法中的工作是弄清楚如何产生q _k,a _k和b _k.

Answer 2

使用平衡二叉搜索树（或数组中的二分搜索）并获得 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)

该解决方案的优点是实现起来非常简单，但仍然具有较高的复杂性。