当前位置：文江博客话题详情

加载骰子的数据结构？

发布于 2024-10-18 03:21:11 字数 696 浏览 3 评论 0 原文

假设我有一个n面加载骰子，其中每面k都有一定的概率p_{k< /em>} 当我滚动它时就会出现。我很好奇是否有一个好的数据结构来静态存储这些信息（即一组固定的概率），以便我可以有效地模拟骰子的随机滚动。

目前，我有一个 O(lg n) 解决方案来解决这个问题。这个想法是存储所有k前k边的累积概率表，然后生成范围内的随机实数[0, 1) 对表进行二分查找，得到累计值不大于所选值的最大索引。

我更喜欢这个解决方案，但运行时没有考虑概率似乎很奇怪。特别是，在一侧总是出现或值均匀分布的极端情况下，可以使用简单的方法在 O(1) 中生成滚动结果，而我的解决方案仍将采取对数数量的步骤。

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

更新：根据这个问题的答案，我写了一篇文章描述了解决这个问题的多种方法，以及他们的分析。看起来 Vose 的别名方法实现提供了 θ(n) 预处理时间和每次骰子滚动的 O(1) 时间，这确实令人印象深刻。希望这是对答案中包含的信息的有用补充！

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

临风闻羌笛 2024-10-25 03:21:11

您正在寻找别名方法，它提供O(1)一种使用一次性 O(n) 设置生成固定离散概率分布的方法（假设您可以在恒定时间内访问长度为 n 的数组中的条目）。您可以在第 3 章 (PDF) 中找到它的记录luc.devroye.org/rnbookindex.html" rel="noreferrer">“非均匀随机变量生成”，作者：Luc Devroye。

这个想法是采用概率数组 p_k 并生成三个新的 n 元素数组：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_i < s 然后返回 a_i 否则返回 b_i。别名方法的工作是弄清楚如何生成 q_k、a_k 和 b_k。

回复收藏 0 原文

白鸥掠海 2024-10-25 03:21:11

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

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

Use a balanced binary search tree (or binary search in an array) and get O(log n) complexity. Have one node for each die result and have the keys be the interval that will trigger that result.

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)

The good thing about this solution is that is very simple to implement but still has good complexity.

回复收藏 0 原文

梦冥 2024-10-25 03:21:11

我正在考虑将你的桌子颗粒化。

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

I'm thinking of granulating your table.

Instead of having a table with the cumulative for each die value, you could create an integer array of length xN, where x is ideally a high number to increase accuracy of the probability.

Populate this array using the index (normalized by xN) as the cumulative value and, in each 'slot' in the array, store the would-be dice roll if this index comes up.

Maybe I could explain easier with an example:

Using three dice: P(1) = 0.2, P(2) = 0.5, P(3) = 0.3

Create an array, in this case I will choose a simple length, say 10. (that is, 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

Then to get the probability, just randomize a number between 0 and 10 and simply access that index.

This method might loose accuracy, but increase x and accuracy will be sufficient.

回复收藏 0 原文

影子的影子 2024-10-25 03:21:11

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

使用自定义权重函数 f(x) 选择整数的最简单方法之一是拒绝采样方法。以下假设 f 的最高可能值为 max 并且每个权重为 0 或更大。拒绝采样的时间复杂度平均而言是恒定的，但很大程度上取决于分布的形状，并且最坏的情况是永远运行。要使用拒绝采样在 [1, k] 中选择一个整数：

在 [1, k] 中选择一个均匀随机整数 i。
以概率f(i)/max，返回i。否则，转至步骤 1。（例如，如果所有权重均为大于 0 的整数，则在 [1, max] 中选择一个均匀随机整数，如果该数字为 f(i ) 或更少，返回 i，否则转到步骤 1。）

其他算法的平均采样时间不太依赖于分布（通常是常数或对数），但通常需要您在设置步骤中预先计算权重并将其存储在数据结构中。其中一些就平均使用的随机位数而言也很经济。其中许多算法是在 2011 年之后推出的，其中包括

——Bringmann–Larsen 简洁数据结构（“Succinct Sampling from Discrete Distributions”，2012）、
唐云鹏的多级搜索（“An Empirical Study of Random Sampling Method for Change Discrete”） Distributions”，2019），以及
快速加载骰子滚轮（2020）。

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