14

假设给您三个“选项” A，B和C。

您的算法必须选择并返回一个随机的。为此，只需将它们放入一个数组{A,B,C}并生成一个随机数（0、1 或 2），这将是要返回的数组中元素的索引，这是非常简单的。

现在，这个算法有一个变种：假设A有 40% 的机会被选中，B一个 20% 和C一个 40%。如果是这种情况，您可以采用类似的方法：生成一个数组{A,A,B,C,C}并使用一个随机数 (0, 1, 2, 3, 4) 来选择要返回的元素。

这样可行。但是，我觉得它非常低效。想象一下将这个算法用于大量选项。您将创建一个有点大的数组，可能有 100 个元素，每个元素代表 1%。现在，这仍然不是很大，但是假设您的算法每秒使用多次，这可能会很麻烦。

我考虑过创建一个名为 的类Slot，它有两个属性：.value和.size. 为每个选项创建一个槽，其中.value属性是选项的值，.size一个等于数组中此类选项的出现次数。然后生成一个从 0 到总出现次数的随机数，并检查该数字落在哪个插槽上。

我更关心算法，但这是我的 Ruby 尝试：

class Slot
  attr_accessor :value
  attr_accessor :size
  def initialize(value,size)
    @value = value
    @size  = size
  end
end

def picker(options)
  slots = []
  totalSize = 0
  options.each do |value,size|
    slots << Slot.new(value,size)
    totalSize += size
  end
  pick = rand(totalSize)
  currentStack = 0
  slots.each do |slot|
    if (pick <= currentStack + slot.size)
      return slot.value
    else
      currentStack += slot.size
    end
  end
  return nil
end

50.times do
  print picker({"A" => 40, "B" => 20, "C" => 40})
end

哪个输出：

CCCCACCCCAAACABAAACACACCCAABACABABACBAAACACCBACAAB

是否有更有效的方法来实现选择随机选项的算法，其中每个选项都有不同的被选择概率？

4

3 回答 3

18

最简单的方法大概就是写一个case语句：

def get_random()
  case rand(100) + 1
    when  1..50   then 'A'
    when 50..75   then 'B'
    when 75..100  then 'C'
  end
end

这样做的问题是你不能传递任何选项，所以如果你希望它能够接受选项，你可以编写这样的函数。下面这个和你写的很像，但是短一点：

def picker(options)
  current, max = 0, options.values.inject(:+)
  random_value = rand(max) + 1
  options.each do |key,val|
     current += val
     return key if random_value <= current
  end
end

# A with 25% prob, B with 75%.
50.times do
  print picker({"A" => 1, "B" => 3})
end
# => BBBBBBBBBABBABABBBBBBBBABBBBABBBBBABBBBBBABBBBBBBA

# If you add upp to 100, the number represent percentage.
50.times do
  print picker({"A" => 40, "T" => 30, "C" => 20, "G" => 10})
end
# => GAAAATATTGTACCTCAATCCAGATACCTTAAGACCATTAAATCTTTACT
于 2013-10-09T07:30:53.263 回答
8

作为更有效算法的第一个近似值，如果您计算累积分布函数（这只是对分布函数的一次传递，计算运行总和），那么您可以使用二进制搜索找到随机选择的整数的位置的线性搜索。如果您有很多选项，这将有所帮助，因为它将搜索时间从 O(#options) 减少到 O(log #options)。

不过，有一个 O(1) 的解决方案。这是基本轮廓。

假设我们有 N 个选项，1...N，权重，其中所有 ω 值至少为 0。为简单起见，我们缩放权重，使其平均值为，或者换句话说，它们的总和为。（我们只是将它们乘以。我们实际上不必这样做，但它使接下来的几段更容易在没有 MathJax 的情况下键入。）ω1...ωN1NN/Σω

现在，创建一个N元素向量，其中每个元素都有两个选项标识符 ( loand hi) 和一个 cutoff p。选项标识符只是整数1...N，并将p计算为包含范围内的实数(0, 1.0)。

我们继续填写向量如下。i依次对每个元素：

  • 如果 some正好是，那么我们设置： 并且我们从权重列表中删除。ωj1.0
       loi = j
       hii = j
       pi = 1.0
    ωj

  • 否则，一定有 some和 some 。（那是因为平均权重是1.0，没有一个有平均值。有些肯定少有些多，因为不可能所有元素都大于平均值或所有元素都小于比平均值。）现在，我们设置： 再一次，我们从权重中删除。ωj < 1.0ωk > 1.0
       loi = j
       hii = k
       pi = ωj
       ωk = ωk - (1 - ωj)
    ωj

请注意，在这两种情况下，我们都删除了一个权重，并且我们将权重总和减少了 1.0。所以平均权重还是1.0。

我们以这种方式继续，直到整个向量被填满。（最后一个元素将具有p = 1.0）。

给定这个向量，我们可以选择一个加权随机选项，如下所示：

  • 生成范围内的随机整数i和范围内的1...N随机浮点值。如果那么我们选择 option ; 否则，我们选择 option 。r(0, 1.0]r < piloihii

应该清楚为什么这从向量的构造中起作用。每个高于平均权重的选项的权重分布在各个向量元素中，而每个低于平均权重的选项被分配给具有相应选择概率的某个向量元素的一部分。

在实际实现中，我们会将权重范围映射到整数值，并使总权重接近最大整数（它必须是 的倍数N，所以会有一些晃动。）然后我们可以选择一个插槽并从单个随机整数中选择槽内的权重。实际上，我们可以通过添加一些 0 加权选项来强制槽数为 2 的幂来修改算法以避免除法。因为整数运算不会完美运行，所以需要进行一些摆弄，但最终结果可以在统计上正确，以所使用的 PRNG 的特性为模，它的执行速度几乎与简单的未加权的选择N选项（一个班次和几个额外的比较），代价是向量占用的存储元素少于6N存储元素（计算必须几乎将插槽数量增加一倍的可能性）。

于 2013-10-09T01:39:53.263 回答
7

虽然这不是一个直接的答案，但我会向您展示帮助您概述此问题的来源：http ://www.av8n.com/physics/arbitrary-probability.htm 。

编辑：

刚刚在 ruby​​ 中找到了一个很好的来源，picking gem。

require 'pickup'
headings = {
  A: 40,
  B: 20,
  C: 40,
}
pickup = Pickup.new(headings)
pickup.pick
#=> A
pickup.pick
#=> B
pickup.pick
#=> A
pickup.pick
#=> C
pickup.pick
#=> C
于 2013-10-09T01:27:54.553 回答