algorithm - 随机选择具有频率的项目的高效算法

Question

给定一个数组 n词频对:

[ (w0, f0), (w1, f1), ..., (wn-1, fn-1) ]

哪里w<sub>i</sub>是一个词，f<sub>i</sub>是整数频率，频率之和∑f<sub>i</sub> = m ,

我想使用伪随机数生成器 (pRNG) 来选择 p话 w<sub>j<sub>0</sub></sub>, w<sub>j<sub>1</sub></sub>, ..., w<sub>j<sub>p-1</sub></sub>这样选择任何单词的概率与其频率成正比:

P(wi = wjk) = P(i = jk) = fi / m

(注意，这是带替换的选择，所以每次都可能选择同一个词)。

到目前为止，我提出了三种算法:

1. 创建一个大小为 m 的数组, 并填充它所以第一个 f<sub>0</sub>条目是 w<sub>0</sub> , 下一个 f<sub>1</sub>条目是 w<sub>1</sub> ，等等，所以最后一个 f<sub>p-1</sub>条目是 w<sub>p-1</sub> .

   [ w0, ..., w0, w1,..., w1, ..., wp-1, ..., wp-1 ]

   然后使用 pRNG 选择 p 0...m-1 范围内的指数，并报告存储在这些索引处的单词。
   这需要 O(n + m + p)工作，这不是很好，因为m可以比 n 大得多。

2. 遍历输入数组一次，计算

   mi = ∑h≤ifh = mi-1 + fi

   计算后 m<sub>i</sub> , 使用 pRNG 生成一个数字 x<sub>k</sub>在 0...m<sub>i</sub>-1 范围内对于每个 k在0...p-1并选择 w<sub>i</sub>对于 w<sub>j<sub>k</sub></sub> (可能替换 w<sub>j<sub>k</sub></sub> 的当前值)如果 x<sub>k</sub> < f<sub>i</sub> .
   这需要 O(n + np)工作。

3. 计算 m<sub>i</sub>与算法 2 一样，在 n 个词频部分和三元组上生成以下数组:

   [ (w0, f0, m0), (w1, f1, m1), ..., (wn-1, fn-1, mn-1) ]

   然后，对于 0...p-1 中的每个 k , 使用 pRNG 生成一个数字 x<sub>k</sub>在 0...m-1 范围内然后对三元组数组进行二进制搜索以找到 i英石。 m<sub>i</sub>-f<sub>i</sub> ≤ x<sub>k</sub> < m<sub>i</sub> , 然后选择 w<sub>i</sub>对于 w<sub>j<sub>k</sub></sub> .
   这需要 O(n + p log n)工作。

我的问题是:是否有更高效的算法可以用于此目的，或者这些算法是否已达到最佳状态？

Answer 1

这听起来像轮盘赌选择，主要用于遗传/进化算法中的选择过程。

看Roulette Selection in Genetic Algorithms