3

我正在尝试制作一个使用 Monte Carlo Hit 或 Miss Simulation 的随机发生器。

我有一个表示 ID 和概率值的键值对：

ID - Value
2  - 0.37
1 - 0.35
4 - 0.14
3 - 0.12

当您添加所有这些值时，您将得到 1.0。

您可以将这些值想象为“轮”上“切片”的总面积（例如：ID 2 占轮子的 37%，而 ID 3 仅占轮子的 12%）。当转换为“范围”时，它将如下所示：

ID - Value - Range
2  - 0.37 - 0 to 37
1 - 0.35 - 37 to 72
4 - 0.14 - 72 to 86
3 - 0.12- 86 to 100

现在，我使用 Random.NextDouble() 来生成一个介于 0.0 和 1.0 之间的随机值。该随机值将被视为车轮上的“旋转”。比如说，随机化器返回 0.35，然后将选择 ID 2。

鉴于我有一个双打数组，实现这一点的最佳方法是什么？

4

5 回答 5

4

最简单的解决方案通常是最好的，如果您的范围设计为 0 - 100（或另一个可管理的小数字），您可以分配int[]并使用您创建的范围表来填写相应索引处的 ID，您的“抛出"然后看起来像：

int randomID = rangesToIDs[random.nextInt(rangesToIDs.length)];

顺便说一句，没有必要根据范围大小对 ID 进行排序，因为假定随机数是均匀分布的，因此在查找表中放置范围的位置并不重要。重要的是条目的数量与抛出 ID 的机会成正比。

于 2009-11-18T09:06:33.790 回答
1

假设您的初始数据表示为数组 D[n]，其中 D[i] = (id, p) 和 sum(D[i].p for i=0..n-1) == 1。

构建第二个数组 P[n] 使得 P[i] = (q, id): P[i] = (sum(D[j].p for j in 0..i), D[j].id ) -- 即将每个切片 i 的单个概率转换为 i 之前的所有切片的累积概率（包括在内）。请注意，根据定义，该数组 P 按字段 q 排序（即按累积概率）。

现在您可以使用二分搜索来查找随机数 r (0 <= r <= 1) 选择的切片：

找到最高的 i 使得 P[i].q <= r; 那么 P[i].id 就是你的切片。

通过使用固定网格对概率范围进行散列处理，可以进一步加快查找速度。如果有人感兴趣，我可以写更多的细节。

于 2009-11-18T09:27:44.377 回答
0

以“Value”为键、“ID”为值的排序地图/字典将允许您快速找到您所在范围的上限，然后查找该范围的 ID

假设您的字典允许它，那么二进制搜索会更好地找到上限而不是遍历整个字典

于 2009-11-18T08:58:55.553 回答
0 
boundaries = [37, 72, 86, 100]
num = 100 * random
for i in boundaries:
  if num < i then return i
于 2009-11-18T10:13:22.510 回答
0

正如 jk 写的那样，排序字典应该没问题。

假设你有这样的字典：

0.37 2
0.72 1
0.86 4
1.00 3

你滚动 xx = 0.66.. 如果 xx < dict[i].key 返回 dict[i].value，则从最小数字（即 0.37）开始遍历字典

或者我想到的另一个解决方案是包含上下限和值的自定义对象列表。然后遍历列表并检查滚动数是否在上下限范围内。

于 2009-11-18T09:19:58.240 回答