Sampling Schlüssel aufgrund ihrer Werte

Question

Ich habe ein Wörterbuch in Python mit Key-> Wert als str->int. Wenn ich einen Schlüssel auf seinen eigenen Wert basiert gewählt haben, dann, wenn der Wert größer wird der Schlüssel hat eine geringere Möglichkeit gewählt zu werden.

Zum Beispiel, wenn key1=2 und key2->1, dann ist die Haltung der key1 sollte 2:1 sein.

Wie kann ich das tun?

Answer 1

1 Erstellen Sie eine CDF-ähnliche Liste wie folgt aus:.

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

Diese Funktion gibt ein Tupel, ist der erste Wert die Summe der Wahrscheinlichkeiten und zweiter Wert ist der CDF.

2 Konstruieren der Sampler wie folgt aus:.

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]

Verbrauch:

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

Sie möchten diese in eine Klasse machen.

Answer 2

Sind die Werte zu groß für gnibler Ansatz:

Erstellen Sie eine Liste von Tupeln (key, index), wo index die Summe aller Werte, die in der Liste, bevor Schlüssel kommen (dies würde der Index des ersten Auftretens der Liste key c gnibler ist. Außerdem ist die Summe aller Werte berechnen (n ).

Nun erzeugt eine Zufallszahl xbetween 0 und n - 1. Finden Sie den letzten Eintrag in der Liste mit index < x. Da die Liste von Index sortiert ist, können Sie binäre Suche verwenden, um das effizient zu tun.

Update: KennyTM Code ist eine Implementierung dieses, außer dass er eine Brute-Force nutzt anstelle von binären Such linear zu suchen; dies ineffizient sein wird, wenn die Anzahl der Tasten sind groß.

Answer 3

Es sind die Werte nicht zu groß ist, können Sie es auf diese Weise tun

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

Eine schnelle und einfache Version des Algorithmus von oefe der und KennyTM die Antworten:

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