रैंडम अजगर शब्दकोश कुंजी, मूल्यों

Question

मैं एक शब्दकोश जहां प्रत्येक कुंजी चर लंबाई की एक सूची है, जैसे है के आधार पर भारित:

d = { 
'a': [1, 3, 2], 
'b': [6], 
'c': [0, 0] 
} 

वहाँ एक यादृच्छिक शब्दकोश कुंजी प्राप्त करने के लिए एक साफ रास्ता, लंबाई के आधार पर भारित है इसके मूल्य का? random.choice(d.keys()) चाबियों को समान रूप से वज़न देगा, लेकिन ऊपर दिए गए मामले में मुझे 'a' लगभग आधा समय लौटाया जाना चाहिए।

Answer 1

यह काम करेगा:

random.choice([k for k in d for x in d[k]]) 

Answer 2

एक सूची है, जिसमें प्रत्येक कुंजी अपने मूल्य की लंबाई के बराबर कई बार दोहराया गया है। आपके उदाहरण में: ['a', 'a', 'a', 'b', 'c', 'c']। फिर random.choice() का उपयोग करें।

संपादित करें: या, कम सुंदरता से अधिक कुशलतापूर्वक, इसे आज़माएं: शब्दकोश में सभी मानों की लंबाई का योग लें, S (आप इस मान को कैश और अमान्य कर सकते हैं, या इसे संपादित करते समय इसे अद्यतित कर सकते हैं शब्दकोश, सटीक उपयोग पैटर्न के आधार पर आप अनुमान लगाते हैं)। 0 से एस तक यादृच्छिक संख्या उत्पन्न करें, और उस श्रेणी को खोजने के लिए शब्दकोश कुंजी के माध्यम से एक रैखिक खोज करें जिसमें आपका यादृच्छिक संख्या गिरती है।

मुझे लगता है कि आप अपने डेटा प्रतिनिधित्व को बदलने या जोड़ने के बिना सबसे अच्छा कर सकते हैं।

Answer 3

क्या आप हमेशा शब्दकोश में मूल्यों की कुल संख्या जानते हैं? कुंजी की अपनी सूची से अधिक

1. दोहराएं: यदि हां, तो इस निम्नलिखित एल्गोरिथ्म, जो इस्तेमाल किया जा सकता के साथ क्या करने के लिए आसान है जब भी आप एक आदेश दिया सूची से कुछ मदों की एक संभाव्य चयन बनाना चाहते हो सकता है।
2. 0 और 1 (उर्फ "पासा रोल") के बीच समान रूप से वितरित यादृच्छिक मान उत्पन्न करें।
3. मानते हैं कि इस कुंजी के साथ जुड़े एन_वीएएलएस मान हैं और पूरे शब्दकोश में TOTAL_VALS कुल मान हैं, इस कुंजी को संभाव्यता N_VALS/N_REMAINING के साथ स्वीकार करें, जहां N_REMAINING सूची में छोड़ी गई वस्तुओं की संख्या है।

इस एल्गोरिदम का कोई भी नया सूचियां उत्पन्न करने का लाभ नहीं है, जो महत्वपूर्ण है यदि आपका शब्दकोश बड़ा है। आपका प्रोग्राम केवल कुल की गणना करने के लिए के कुंजी पर लूप के लिए भुगतान कर रहा है, चाबियों पर एक और लूप जो औसत अंत में आधा रास्ते पर होगा, और 0 और 1 के बीच यादृच्छिक संख्या उत्पन्न करने के लिए जो कुछ भी खर्च होता है, वह इस तरह की यादृच्छिक संख्या उत्पन्न करना है प्रोग्रामिंग में एक बहुत ही आम अनुप्रयोग है, इसलिए अधिकांश भाषाओं में ऐसे फ़ंक्शन का तेज़ कार्यान्वयन होता है। पाइथन में random number generatorMersenne Twister algorithm का सी कार्यान्वयन, जो बहुत तेज़ होना चाहिए। इसके अतिरिक्त, दस्तावेज़ीकरण का दावा है कि यह कार्यान्वयन थ्रेड-सुरक्षित है।

यहां कोड है।

{'a': 49801, 'c': 33548, 'b': 16650} 

:

#!/usr/bin/python 

import random 

def select_weighted(d): 
    # calculate total 
    total = 0 
    for key in d: 
     total = total + len(d[key]) 
    accept_prob = float(1.0/total) 

    # pick a weighted value from d 
    n_seen = 0 
    for key in d: 
     current_key = key 
     for val in d[key]: 
     dice_roll = random.random() 
     accept_prob = float(1.0/(total - n_seen)) 
     n_seen = n_seen + 1 
     if dice_roll <= accept_prob: 
      return current_key 

dict = { 
    'a': [1, 3, 2], 
    'b': [6], 
    'c': [0, 0] 
} 

counts = {} 
for key in dict: 
    counts[key] = 0 

for s in range(1,100000): 
    k = select_weighted(dict) 
    counts[k] = counts[k] + 1 

print counts 

इस 100 बार चलाने के बाद, मैं चयन कुंजी कई बार इस नंबर मिल: मुझे यकीन है कि आप इसे साफ आप अधिक pythonic सुविधाओं का उपयोग करना चाहते हैं तो कर सकते हैं

{'a': 0.5, 'c': 0.33333333333333331, 'b': 0.16666666666666666} 

संपादित करें:: उन काफी की अपनी उम्मीद मूल्यों के करीब हैं मीलों अपने मूल कार्यान्वयन, जो बाद से सही किया गया है में एक गंभीर त्रुटि बताया। उसके लिए माफ़ करना!

Answer 4

यह देखते हुए कि आपका निर्देश स्मृति में फिट बैठता है, यादृच्छिक। चॉइस विधि उचित होना चाहिए। लेकिन अन्यथा मानते हुए, अगली तकनीक बढ़ते वजन की एक सूची का उपयोग करना है, और बेतरतीब ढंग से चुने हुए वजन को खोजने के लिए bisect का उपयोग करना है।

>>> import random, bisect 
>>> items, total = [], 0 
>>> for key, value in d.items(): 
     total += len(value) 
     items.append((total, key)) 


>>> items[bisect.bisect_left(items, (random.randint(1, total),))][1] 
'a' 
>>> items[bisect.bisect_left(items, (random.randint(1, total),))][1] 
'c' 

Answer 5

यहाँ कुछ कोड है कि पिछले एक जवाब मैं probability distribution in python के लिए दे दी है पर आधारित है, लेकिन लंबाई उपयोग कर रहा है वजन स्थापित करने के लिए है। यह एक पुनरावृत्ति मार्कोव श्रृंखला का उपयोग करता है ताकि उसे यह जानने की आवश्यकता न हो कि वजन के कुल क्या हैं। वर्तमान में यह अधिकतम लंबाई की गणना करता है, लेकिन यह है कि अगर बहुत धीमी है सिर्फ

self._maxw = max lenght 

को

self._maxw = 1 

बदल सकते हैं और हटाने

for k in self._odata: 
    if len(self._odata[k])> self._maxw: 
      self._maxw=len(self._odata[k]) 

यहाँ कोड है।

import random 


class RandomDict: 
    """ 
    The weight is the length of each object in the dict. 
    """ 

    def __init__(self,odict,n=0): 
     self._odata = odict 
     self._keys = list(odict.keys()) 
     self._maxw = 1 # to increase speed set me to max length 
     self._len=len(odict) 
     if n==0: 
      self._n=self._len 
     else: 
      self._n=n 
     # to increase speed set above max value and comment out next 3 lines 
     for k in self._odata: 
      if len(self._odata[k])> self._maxw: 
       self._maxw=len(self._odata[k]) 


    def __iter__(self): 
     return self.next() 

    def next(self): 
     while (self._len > 0) and (self._n>0): 
      self._n -= 1 
      for i in range(100): 
       k=random.choice(self._keys) 
       rx=random.uniform(0,self._maxw) 
       if rx <= len(self._odata[k]): # test to see if that is the value we want 
        break 
      # if you do not find one after 100 tries then just get a random one 
      yield k 

    def GetRdnKey(self): 
     for i in range(100): 
      k=random.choice(self._keys) 
      rx=random.uniform(0,self._maxw) 

      if rx <= len(self._odata[k]): # test to see if that is the value we want 
       break 
     # if you do not find one after 100 tries then just get a random one 
     return k 



#test code 

d = { 
'a': [1, 3, 2], 
'b': [6], 
'c': [0, 0] 
} 


rd=RandomDict(d) 

dc = { 
'a': 0, 
'b': 0, 
'c': 0 
} 
for i in range(100000): 
    k=rd.GetRdnKey() 
    dc[k]+=1 

print("Key count=",dc) 



#iterate over the objects 

dc = { 
'a': 0, 
'b': 0, 
'c': 0 
} 

for k in RandomDict(d,100000): 
    dc[k]+=1 

print("Key count=",dc) 

टेस्ट परिणाम

Key count= {'a': 50181, 'c': 33363, 'b': 16456} 
Key count= {'a': 50080, 'c': 33411, 'b': 16509} 

Answer 6

मैं यह कहना चाहते हैं:

random.choice("".join([k * len(d[k]) for k in d])) 

यह यह स्पष्ट घ में प्रत्येक कश्मीर अपने मूल्य की लंबाई के रूप में और भी अधिक अवसर हो जाता है कि बनाता है। बेशक, यह लंबाई 1 है कि चरित्र का शब्दकोश कुंजी पर

---

काफी समय बाद भरोसा है ....:

table = "".join([key * len(value) for key, value in d.iteritems()]) 
random.choice(table) 

Answer 7

दोहराया मूल्यों के साथ एक नया, संभवतः बड़ी सूची निर्माण के बिना:

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 

Answer 8

मैंने कुछ अन्य उत्तरों को इसके साथ आने के लिए संशोधित किया। यह थोड़ा और विन्यास योग्य है। इसमें 2 तर्क, एक सूची और एक लैम्ब्डा फ़ंक्शन होता है ताकि यह बताने के लिए कि कुंजी कैसे उत्पन्न करें।

def select_weighted(lst, weight): 
    """ Usage: select_weighted([0,1,10], weight=lambda x: x) """ 
    thesum = sum([weight(x) for x in lst]) 
    if thesum == 0: 
     return random.choice(lst) 
    offset = random.randint(0, thesum - 1) 

    for k in lst: 
     v = weight(k) 
     if offset < v: 
     return k 
     offset -= v 

इसके लिए बेस कोड के लिए sth के लिए धन्यवाद।