2

我想根据给定的概率从哈希表中选择一个项目。例如,我将字符串“apple”“banana”和“pineapple”存储到我的哈希表中。现在我想根据他们给定的概率从哈希表中取出一个项目,说得到“苹果”的概率是 30%,一个“香蕉”是 30%,一个“菠萝”是 40%。谁能帮我解决这个问题?

我需要使用 Hashtable 的原因是我实际上正在处理大量字符串,这些字符串是某本书中的单词。单词出现的概率取决于它在书中的出现。例如,如果某本书有 100,000 个单词,而“dog”这个词出现了 1,000 次。当我从我的函数调用时,我得到一条“狗”的概率应该是 1,000/100,000。

4

2 回答 2

2

这是您的项目数组:

[apple, banana, pineapple]

这是您的概率数组:

[0.3, 0.3, 0.4]

这是您的累积概率数组:

[0.3, 0.6, 1.0]

要根据概率选择一个随机项目,请在 [0, 1] 范围内选择一个随机数 R,然后选择累积概率大于或等于 R 的第一个项目。

例如,如果生成 R = 0.52839,则选择香蕉,因为 0.6 是累积概率大于或等于 R 的第一项。

您可以对 R 指定的项目进行二分搜索,因此这是一个 log(n) 解决方案。

我不知道哈希表会以何种方式帮助您。简单的数组就足够了。

于 2013-11-05T18:10:28.780 回答
1

您应该考虑使用别名表。这是处理大量不等概率的一种非常有效的方法。

于 2013-11-05T20:31:20.207 回答