مفاتيح أخذ العينات بسبب قيمها

Question

لديّ قاموس في بيثون مع مفتاح> قيمة 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)

تقوم هذه الوظيفة بإرجاع 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

قد ترغب في جعل هذا في فصل.

Answer 2

إذا كانت القيم كبيرة جدًا لنهج Gnibler:

بناء قائمة من tuples (key, index), ، أين index هو مجموع جميع القيم التي تأتي قبل المفتاح في القائمة (سيكون هذا فهرس الحدوث الأول key قائمة Gnibler c. احسب أيضًا مجموع جميع القيم (n).

الآن ، قم بإنشاء رقم عشوائي xبين 0 و 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'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