Sampling Schlüssel aufgrund ihrer Werte
-
21-09-2019 - |
Frage
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?
Lösung
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.
Andere Tipps
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 x
between 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ß.
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
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