假设我有一个n侧加载的模具,当我滚动它时,每个侧面k都有一些概率p k.我很好奇是否存在静态存储此信息的良好算法(即,对于一组固定的概率),以便我可以有效地模拟模具的随机滚动.
目前,我有一个针对此问题的O(lg n)解决方案.想法是存储所有k的前k个边的累积概率的表,它们生成范围[0,1)中的随机实数并且对表执行二元搜索以获得其累积的最大索引值不大于所选值.我更喜欢这个解决方案,但运行时没有考虑概率似乎很奇怪.特别是,在一方总是出现或值均匀分布的极端情况下,可以使用朴素的方法在O(1)中生成滚动的结果,尽管我的解决方案仍然需要采用多个步骤的对数.
有没有人对如何以某种方式在运行时"自适应"的方式解决这个问题有任何建议？
编辑:基于这个问题的答案,我写了一篇文章,描述了这个问题的许多方法,以及他们的分析.看起来Vose的别名方法的实现给出了Θ(n)预处理时间和每次掷骰的O(1)时间,这确实令人印象深刻.希望这是对答案中包含的信息的有用补充!
language-agnostic random algorithm probability data-structures