我想根据哈希表中给定的概率选取一个项目。 例如,我将字符串“apple”“banana”和“pineapple”存储到我的哈希表中。现在我想根据给定的概率从哈希表中取出一个项目,假设得到“苹果”的概率是 30%,“香蕉”是 30%,“菠萝”是 40%。谁能帮我解决这个问题吗?
我需要使用哈希表的原因是我实际上正在处理大量的字符串,这些字符串是某本书中的单词。该单词的概率取决于它在书中出现的情况。例如,某本书有 100,000 个单词,“狗”这个词出现了 1,000 次。当我从函数中调用时,得到“狗”的概率应该是 1,000/100,000。
最佳答案
这是您的项目数组:
[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) 解决方案。
我不知道哈希表能以什么方式帮助你。简单的数组就足够了。
关于random - 根据哈希表中的概率选取一个项目,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19795472/