加载骰子的数据结构？

假设我有一个 N面加载的骰子，其中每一面 K都有一定的概率 P < sub > K 当我掷骰子时出现。我很好奇是否有一个好的数据结构来静态地存储这些信息(例如，对于一组固定的概率) ，这样我就可以有效地模拟随机的骰子。

目前，我有一个 O (lgN)解决这个问题。这个想法是存储所有 K的第一个 K边的累积概率表，然后在范围[0,1)内生成一个随机实数，并对表进行二进制搜索，以获得累积值不大于所选值的最大索引。

我非常喜欢这个解决方案，但是运行时没有考虑到这种可能性似乎有点奇怪。特别是，在极端情况下，如果一边总是出现或者值是均匀分布的，可以使用简单的方法在 O (1)中生成滚动的结果，而我的解决方案仍然需要对数多个步骤。

有人对如何在运行时以某种“适应性”的方式解决这个问题有什么建议吗？

更新: 根据对这个问题的回答，我写了 一篇描述解决这个问题的许多方法的文章，以及他们的分析。看起来 Vose 对 alias 方法的实现给出了 Θ (N)的预处理时间和每个骰子辊的 O (1)时间，这真是令人印象深刻。希望这是对包含在答案中的信息的一个有用的补充！

13922 次浏览
小开

我在考虑给你的桌子做颗粒。

您可以创建一个长度为 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 和准确性就足够了。

小开

使用平衡二叉查找树(或数组中的二进制搜索) ，得到 O (logn)复杂度。每个骰子结果有一个节点，键是触发该结果的时间间隔。

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)

这个解决方案的好处是实现起来非常简单，但是仍然具有很好的复杂性。

小开
最佳答案

你正在寻找的是 别名法别名法，它提供了一种 O (1)方法，通过一次性 O (n)设置来生成一个固定的离散概率分布(假设你可以在恒定时间内访问长度为 n 的数组中的条目)。你可以在 Luc Devroye 的 “非均匀随机变量生成”的 第三章(PDF)中找到它的记录。

其思想是利用概率数组 pK生成三个新的 n 元素数组 qK aK和 bK。每个 qK是介于0和1之间的概率，每个 aK和 bK是介于1和 n 之间的整数。

我们通过生成两个介于0和1之间的随机数 r 和 s 来生成介于1和 n 之间的随机数。设 i = floor (r * N) + 1。如果 q我 < s，则返回 a我，否则返回 b我。别名方法的工作是弄清楚如何生成 qK、 aK和 bK。

小开

使用自定义分布(也称为 离散分布)生成随机整数的方法有很多种。选择取决于很多因素，包括可供选择的整数数量、分布的形状以及分布是否会随时间而改变。

使用自定义权重函数 f(x)选择整数的最简单方法之一是 废弃物取样方法。下面假设 f的最高可能值是 max，每个权重为0或更大。剔除采样的时间复杂度平均不变，但与分布的形状有很大关系，并且有永远运行的最坏情况。使用拒绝采样在[1，k]中选择一个整数:

  1. 在[1，k]中选择一个统一的随机整数 i。
  2. 以概率 f(i)/max返回 i。否则，转到步骤1。(例如，如果所有的权重都是大于0的整数，那么在[1，max]中选择一个统一的随机整数，如果该数字是 f(i)或更小，则返回 i，否则转到步骤1。)

其他算法的平均采样时间不太依赖于分布(通常是常数或对数) ，但通常需要在设置步骤中预先计算权重并将其存储在数据结构中。它们中的一些在平均使用的随机位数方面也是经济的。这些算法中有许多是在2011年以后引入的，其中包括ー

  • Bringmann-Larsen 的简洁数据结构(“离散分布的简洁抽样”，2012) ,
  • 唐的多层次搜索(“随机抽样方法改变离散分布的实证研究”，2019) ，和
  • 快速加载骰子滚筒(2020).

其他算法包括 别名法别名法(在您的文章中已经提到过)、 Knuth-Yao 算法、 MVN 数据结构等。请参阅我的“ 带替换的加权选择”部分进行调查。


提交答案