16

我有一个由 N 个元素组成的数组（代表给定字母表的 N 个字母），并且该数组的每个单元格都保存一个整数值，该整数值表示该字母在给定文本中出现的次数。现在我想根据他在给定约束下出现的次数从字母表中的所有字母中随机选择一个字母：

  • 如果字母具有正（非零）值，则算法始终可以选择它（当然，概率更大或更小）。

  • 如果字母 A 的值高于字母 B，则算法必须更可能选择它。

现在，考虑到这一点，我想出了一个可以完成这项工作的简单算法，但我只是想知道是否有更好的事情要做。这似乎是非常基本的，我认为为了更有效地完成这一点，可能需要做更多聪明的事情。这是我认为的算法：

  • 将数组中的所有频率相加。将其存储在 SUM 中
  • 选择从 0 到 SUM 的随机值。将其存储在 RAN 中
  • [While] RAN > 0，从第一个开始，访问数组中的每个单元格（按顺序），并从RAN中减去该单元格的值
  • 最后访问的单元格是选择的单元格

那么，还有比这更好的事情吗？我错过了什么吗？

我知道大多数现代计算机可以如此快速地计算这个，如果我的算法效率低下，我什至不会注意到，所以这更多是一个理论问题，而不是一个实际问题。

我更喜欢解释算法，而不仅仅是代码的答案，但如果你更愿意在代码中提供你的答案，我对此没有任何问题。

4

2 回答 2

19

想法：

  • 遍历所有元素并将每个元素的值设置为迄今为止的累积频率。
  • 生成一个介于 1 和所有频率之和之间的随机数
  • 对该数字的值进行二分搜索（找到大于或等于该数字的第一个值）。

例子：

Element    A B C D
Frequency  1 4 3 2
Cumulative 1 5 8 10

生成一个1-10范围内的随机数（1+4+3+2=10，与累积列表的最后一个值相同），进行二分查找，返回值如下：

Number   Element returned
1        A
2        B
3        B
4        B
5        B
6        C
7        C
8        C
9        D
10       D
于 2013-06-22T12:27:43.113 回答
9

Alias 方法为每个生成的值摊销了 O(1) 时间，但每次查找需要两个制服。基本上，您创建一个表，其中每列包含要生成的值之一、称为别名的第二个值以及在值及其别名之间进行选择的条件概率。使用您的第一个制服选择任何具有相同可能性的列。然后根据您的第二个制服在主要值和别名之间进行选择。最初为 n 个值建立一个有效的表需要 O(n log n) 的工作，但在表的构建后生成值是恒定的时间。您可以下载这个 Ruby gem来查看实际的实现。

Marsaglia 等人的另外两种非常快速的方法。在这里描述。他们提供了C 实现。

于 2013-06-22T17:18:44.143 回答