高效的算法随机选择频率项目

Question

给定一组n字频对:

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

在哪里是一个单词,是整数频率,以及频率的总和,wifi∑fi = m

我想使用伪随机数生成器(pRNG)来选择p单词,以便选择任何单词的概率与其频率成正比:wj0, wj1, ..., wjp-1

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

(注意,这是替换选择,因此每次都可以选择相同的单词).

到目前为止,我已经提出了三种算法:

1. 创建一个大小数组m,并填充它以便第一个条目,下一个条目,等等,所以最后的条目是.f0w0f1w1fp-1wp-1

   [ 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

   和计算之后,使用PRNG以生成数的范围内对每个在 与选择用于(可能替换的当前值,如果). 这需要工作.mixk0...mi-1k0...p-1wiwjkwjkxk < fi
O(n + np)

3. 如算法2中那样计算,并在n个字频 - 部分和三元组上生成以下数组:mi

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

   然后,对于每个k中0...p-1,使用PRNG以生成数的范围内,然后做三元找到的阵列上的二进制搜索ST ,并选择对. 这需要工作.xk0...m-1imi-fi ≤ xk < miwiwjk
O(n + p log n)

我的问题是:我是否可以使用更有效的算法,或者这些算法是否可以获得？

Answer 1

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

看看遗传算法中的轮盘选择

Answer 2

好吧，我找到了另一种算法：别名方法（在这个答案中也提到了）。基本上它创建了概率空间的划分，使得：

• 有n分区，所有分区的宽度都r相同nr = m。
• 每个分区包含一定比例的两个单词（与分区一起存储）。
• 对于每个单词，wifi = ∑partitions t s.t wi ∈ t r × ratio(t,wi)

由于所有分区的大小相同，因此可以在持续工作中选择哪个分区（随机选择一个索引0...n-1），然后可以使用分区的比率来选择在持续工作中使用哪个单词（比较 pRNG 的数字）以及两个词之间的比例）。因此，这意味着在给定这样的分区的情况下，p可以在工作中完成选择。O(p)

存在这种划分的原因是存在单词st ，当且仅当存在单词st时，因为 r 是频率的平均值。 wifi < rwi'fi' > r

给定这样的一对，我们可以分别用频率伪词（用概率和表示概率）和调整频率的新词来替换它们。所有单词的平均频率仍然是r，并且上一段的规则仍然适用。由于伪词的频率为r，并且由频率≠r的两个词组成，我们知道，如果我们迭代这个过程，我们永远不会从一个伪词中生成一个伪词，并且这样的迭代必须以a结束n 个伪字的序列，它们是所需的分区。wiwi'w'if'i = rwifi/rwi'1 - fi/rw'i'f'i' = fi' - (r - fi)

为了及时构建这个分区O(n)，

• 遍历单词列表一次，构建两个列表：
  • 频率 ≤ r 的单词之一
  • 频率 > r 的单词之一
• 然后从第一个列表中提取一个单词
  • 如果它的频率= r，则将其制成单元素分区
  • 否则，从另一个列表中提取一个单词，并用它来填充两个单词的分区。然后根据调整后的频率将第二个单词放回第一个或第二个列表中。

如果分区数量很大，这实际上仍然有效q > n（您只需以不同的方式证明它）。如果您想确保 r 是整数，并且无法轻松找到stq的因子，则可以将所有频率填充 因子，因此，它会在 时更新和设置。mq > nnf'i = nfim' = mnr' = mq = n

无论如何，这个算法只需要O(n + p)工作，我必须认为这是最优的。

在红宝石中：

def weighted_sample_with_replacement(input, p)
  n = input.size
  m = input.inject(0) { |sum,(word,freq)| sum + freq }

  # find the words with frequency lesser and greater than average
  lessers, greaters = input.map do |word,freq| 
                        # pad the frequency so we can keep it integral
                        # when subdivided
                        [ word, freq*n ] 
                      end.partition do |word,adj_freq| 
                        adj_freq <= m 
                      end

  partitions = Array.new(n) do
    word, adj_freq = lessers.shift

    other_word = if adj_freq < m
                   # use part of another word's frequency to pad
                   # out the partition
                   other_word, other_adj_freq = greaters.shift
                   other_adj_freq -= (m - adj_freq)
                   (other_adj_freq <= m ? lessers : greaters) << [ other_word, other_adj_freq ]
                   other_word
                 end

    [ word, other_word , adj_freq ]
  end

  (0...p).map do 
    # pick a partition at random
    word, other_word, adj_freq = partitions[ rand(n) ]
    # select the first word in the partition with appropriate
    # probability
    if rand(m) < adj_freq
      word
    else
      other_word
    end
  end
end