14

と の 3 つの「オプション」が与えられたとAしBますC。

アルゴリズムは、ランダムなものを選択して返す必要があります。このために、それらを配列に入れて、{A,B,C}返される配列内の要素のインデックスとなる乱数 (0、1、または 2) を生成するのは非常に簡単です。

さて、このアルゴリズムにはバリエーションがあります: 40% 、20%、A40% の確率で選ばれるとします。その場合は、同様のアプローチを使用できます。配列を生成し、乱数 (0、1、2、3、4) を使用して、返される要素を選択します。BC{A,A,B,C,C}

それはうまくいきます。しかし、それは非常に効率が悪いと感じています。このアルゴリズムを大量のオプションに使用することを想像してください。おそらく、それぞれ 1% を表す 100 個の要素を持つ、やや大きな配列を作成することになります。これはまだそれほど大きくはありませんが、アルゴリズムが 1 秒間に何度も使用されると仮定すると、これは面倒なことになる可能性があります。

とのSlot2 つのプロパティを持つというクラスを作成することを検討しました。各オプションに対して 1 つのスロットが作成されます。ここで、プロパティはオプションの値であり、1 つは配列内のそのようなオプションの出現回数に相当します。次に、0 から出現回数の合計までの乱数を生成し、その数値がどのスロットに該当するかを確認します。.value.size.value.size

私はアルゴリズムについてもっと心配していますが、これが私の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

どの出力:

CCCCACCCCAAACABAAAACACACCCAABACABABACBAAACACCBACAAB

各オプションが選択される確率が異なるランダムなオプションを選択するアルゴリズムを実装するより効率的な方法はありますか?

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

より効率的なアルゴリズムへの最初の近似として、累積分布関数を計算する場合 (これは、分布関数を 1 回通過して実行中の合計を計算するだけです)、代わりに二分探索を使用して、ランダムに選択された整数の位置を見つけることができます。線形検索の。これは、検索時間を O(#options) から O(log #options) に短縮するため、多くのオプションがある場合に役立ちます。

ただし、O(1) ソリューションがあります。これが基本的なアウトラインです。

N 個のオプション があり1...N、重みがあり、すべての ω 値が少なくとも 0 であるとします。簡単にするために、重みをスケーリングして、それらの平均がになるようにします。つまり、それらの合計が になるようにします。(単に を掛けるだけです。実際にこれを行う必要はありませんが、MathJax を使用せずに次のいくつかの段落を入力しやすくなります。)ω1...ωN1NN/Σω

ここで、要素のベクトルを作成しますN。各要素には 2 つのオプション識別子 (loおよびhi) とカットオフがありpます。オプション識別子は単なる整数1...Nでありp、範囲内の実数として計算されます(0, 1.0)。

次のようにベクトルを埋めていきます。要素ごとiに次のようにします。

  • 一部が正確に である場合、次のように設定します。そして、重みのリストから 削除します。ω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 つの重みを削除し、重みの合計を 1.0 減らしたことに注意してください。したがって、平均重みは 1.0 のままです。

ベクトル全体が満たされるまで、この方法を続けます。(最後の要素には がありますp = 1.0)。

このベクトルが与えられると、次のように加重ランダム オプションを選択できます。

  • 範囲内のランダムな整数iと、範囲内1...Nのランダムな浮動小数点値を生成rします(0, 1.0]。次に、オプションを選択します。それ以外の場合は、オプションを選択します。r < piloihii

なぜこれが機能するのかは、ベクトルの構築から明らかです。平均以上の各オプションの重みは、さまざまなベクトル要素に分散されますが、平均以下の各オプションは、対応する選択確率を持つベクトル要素の一部に割り当てられます。

実際の実装では、重みの範囲を整数値にマッピングし、重みの合計を最大整数に近づけます (これは の倍数でなければならないNため、多少のスロッシュが発生します)。その後、スロットを選択して、単一の乱数整数からスロット内の重みを選択します。実際、アルゴリズムを変更して、スロット数を強制的に 2 の累乗にすることで除算を回避できます。整数演算は完全にはうまくいかないため、少しいじる必要がありますが、最終結果は、使用されている PRNG の特性を法として統計的に正しくすることができ、単純な演算とほぼ同じ速度で実行されます。重み付けされていない選択Nオプション (1 つのシフトと余分な比較のカップル) を犠牲にして、ストレージ要素よりも少ないベクトルを占有し6Nます (スロットの数をほぼ 2 倍にしなければならない可能性を数えます)。

于 2013-10-09T01:39:53.263 に答える
7

これは直接的な答えではありませんが、この問題の概要を説明するのに役立つソースを紹介します: http://www.av8n.com/physics/arbitrary-probability.htm。

編集：

そのための素敵なソースをルビーで見つけたところです。

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 に答える