サンプリングキーによりその価値

Question

私は辞書にpythonの鍵->としての価値 str->int.している場合はを選択するための鍵それに基づく独自の価値を、その値が大きめのキーの低い可能性を選択します。

例えば、 key1=2 や key2->1, その姿勢 key1 すべき 2:1.

する方法を教えてください。

Answer 1

1. 構築CDFようなリストのようになります:

def build_cdf(distrib):
    cdf = []
    val = 0
    for key, freq in distrib.items():
        val += freq
        cdf.append((val, key))
    return (val, cdf)

この機能はタプルを返しますが、1日の値の合計と確率、および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

またはクラスです。

Answer 2

の場合は値が大きすぎgniblerのアプローチ:

構築のリストタプル (key, index), では、 index 額のすべての値が以前のキーのリスト(このインデックスで最初に検出 key gniblerのリスト c.計算全ての値の合計(n).

現在、ランダムに生成番号 x0 n - 1.の最後のエントリのリスト index < x.リストのソートインデックスコンサルティングができるバイナリ検索が効果的です。

更新: KennyTMのコードは実装のことによって、力まで線形探索の代わりにバイナリ検索これは非効率な場合はキーの数が大きい。

Answer 3

この値が大きすぎるではありません、あなたはこのようにそれを行うことができます。

>>> 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

Answer 4

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