key->valueが。のPythonの辞書がありますstr->int
。独自の値に基づいてキーを選択する必要がある場合、値が大きくなると、キーが選択される可能性が低くなります。
たとえば、との場合key1=2
、key2->1
の態度はであるkey1
必要があります2:1
。
これどうやってするの?
key->valueが。のPythonの辞書がありますstr->int
。独自の値に基づいてキーを選択する必要がある場合、値が大きくなると、キーが選択される可能性が低くなります。
たとえば、との場合key1=2
、key2->1
の態度はであるkey1
必要があります2:1
。
これどうやってするの?
値が gnibler のアプローチに対して大きすぎる場合:
tuplesのリストを作成します。(key, index)
ここで、 はリスト内の key の前にあるすべての値の合計です (これは、ニブラーのリストindex
の最初の出現のインデックスになります。また、すべての値の合計を計算します ( )。key
c
n
x
次に、 0 ~ の間の乱数を生成しn - 1
ます。でリストの最後のエントリを見つけますindex < x
。リストはインデックスでソートされているため、バイナリ検索を使用して効率的にソートできます。
更新: KennyTM のコードはこれを実装したものですが、彼は二分探索ではなく力ずくの線形探索を使用しています。キーの数が多い場合、これは非効率的です。
値が大きすぎない場合は、このようにすることができます
>>> from random import choice
>>> d={"key1":2,"key2":1}
>>> c=[]
>>> for k,v in d.items():
... c+=[k]*v
...
>>> choice(c)
'key1'
>>> sum(1 for x in range(100) if choice(c)=="key1")
63
>>> sum(1 for x in range(100) if choice(c)=="key2")
36
1.次のように CDF のようなリストを作成します。
def build_cdf(distrib):
cdf = []
val = 0
for key, freq in distrib.items():
val += freq
cdf.append((val, key))
return (val, cdf)
この関数はタプルを返します。最初の値は確率の合計で、2 番目の値は CDF です。
2.サンプラーを次のように構築します。
import random
def sample_from_cdf(val_and_cdf):
(val, cdf) = val_and_cdf;
rand = random.uniform(0, val)
# use bisect.bisect_left to reduce search time from O(n) to O(log n).
return [key for index, key in cdf if index > rand][0]
使用法:
x = build_cdf({"a":0.2, "b":0.3, "c":0.5});
y = [sample_from_cdf(x) for i in range(0,100000)];
print (len([t for t in y if t == "a"])) # 19864
print (len([t for t in y if t == "b"])) # 29760
print (len([t for t in y if t == "c"])) # 50376
これをクラスにしたいかもしれません。
oefe と KennyTM の回答からのアルゴリズムの迅速でシンプルなバージョン:
def select_weighted(d):
offset = random.randint(0, sum(d.itervalues())-1)
for k, v in d.iteritems():
if offset < v:
return k
offset -= v