مفاتيح أخذ العينات بسبب قيمها
-
21-09-2019 - |
سؤال
لديّ قاموس في بيثون مع مفتاح> قيمة str->int
. إذا اضطررت إلى اختيار مفتاح بناءً على قيمته الخاصة ، فكلما تزداد القيمة ، يكون للمفتاح إمكانية اختيار أقل.
على سبيل المثال ، إذا key1=2
و key2->1
, ثم موقف key1
يجب ان يكون 2: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)
تقوم هذه الوظيفة بإرجاع tuple ، والقيمة الأولى هي مجموع الاحتمالات ، والقيمة الثانية هي 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
قد ترغب في جعل هذا في فصل.
نصائح أخرى
إذا كانت القيم كبيرة جدًا لنهج Gnibler:
بناء قائمة من tuples (key, index)
, ، أين index
هو مجموع جميع القيم التي تأتي قبل المفتاح في القائمة (سيكون هذا فهرس الحدوث الأول key
قائمة Gnibler 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
نسخة سريعة وبسيطة من الخوارزمية من إجابات Oefe's و 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