पाइथन की अंतर्निहित हैश डेटा संरचना शब्दकोशों के लिए

Question

मैं एक बहुत बड़ा शब्दकोश बना रहा हूं और मैं यह देखने के लिए कई चेक कर रहा हूं कि कोई कुंजी संरचना में है या नहीं और फिर यह अद्वितीय है या यदि यह समान है तो यह काउंटर को बढ़ा रहा है।

पाइथन शब्दकोशों को संग्रहीत करने के लिए hash data structure का उपयोग करता है (क्रिप्टोग्राफ़िक हैश फ़ंक्शन से भ्रमित नहीं होना चाहिए)। लुकअप ओ (1) हैं, लेकिन यदि हैश टेबल भर गया है तो इसे फिर से बदलना होगा जो बहुत महंगा है।

मेरा प्रश्न है, क्या मैं AVL Binary Search Tree का उपयोग कर बेहतर होगा या एक हैश टेबल पर्याप्त है?

Answer 1

एक ही तरीका है दोनों को लागू करने और जाँच, लेकिन मेरे सूचित अनुमान है कि शब्दकोश में तेजी है, क्योंकि एक द्विआधारी खोज वृक्ष देखने के लिए लागत हे (लॉग (एन)) है हो जाएगा करने के लिए किया जाएगा सुनिश्चित करने के लिए और सम्मिलन, और मुझे लगता है कि परिस्थितियों के सबसे निराशाजनक (जैसे विशाल हैश टकराव) को छोड़कर हैश टेबल का ओ (1) लुकअप कभी-कभी आकार बदल जाएगा।

आप Python dictionary implementation पर एक नज़र डालें, तो आप उस देखेंगे:

1. एक शब्दकोश 8 प्रविष्टियों (PyDict_MINSIZE) के साथ बाहर शुरू होता है;
2. 50,000 या उससे कम प्रविष्टियों वाला एक शब्दकोश जब यह बढ़ता है तो आकार में चौगुनी हो जाती है;
3. 50,000 से अधिक प्रविष्टियों वाला एक शब्दकोश जब यह बढ़ता है तो आकार में युगल होता है;
4. कुंजी हैश शब्दकोश में कैश किए जाते हैं, इसलिए शब्दकोश का आकार बदलते समय उन्हें पुनः संयोजित नहीं किया जाता है।

("NOTES ON OPTIMIZING DICTIONARIES" भी पढ़ने लायक हैं।)

इसलिए यदि आपके शब्दकोश 1,000,000 प्रविष्टियां हैं, तो मुझे विश्वास है कि यह ग्यारह गुना (8 → 32 → 128 → 512 → 2048 → 8192 बदल दिया जाएगा → 32768 → 131072 → 262144 → 524288 → 1048576 → 20 9 7152) आकार के दौरान 2,009,768 अतिरिक्त सम्मिलन की लागत पर। यह एक एवीएल पेड़ में 1,000,000 प्रविष्टियों में शामिल सभी पुनर्वसन की लागत से काफी कम होने की संभावना है।

Answer 2

आइटम बनाम अद्वितीय वस्तुओं का अनुपात क्या है? अद्वितीय वस्तुओं की अपेक्षित संख्या क्या है?

यदि हैश बाल्टी भर जाती है, तो विस्तार करना केवल कुछ स्मृति पुनर्विक्रय का मामला होना चाहिए, न कि रीहाशिंग।

एक गिनती निर्देश का परीक्षण करना बहुत तेज़ और आसान होना चाहिए।

यह भी ध्यान रखें काउंटर वर्ग अजगर के बाद से उपलब्ध 2.7 http://docs.python.org/library/collections.html#counter-objects http://svn.python.org/view?view=rev & संशोधन = 68559

Answer 3

आप सी में अपने स्वयं के डेटा संरचनाओं को लागू करने के लिए होगा अंतर्निहित संरचनाओं को मारने का एक उचित मौका खड़ा करना।

इसके अलावा आप get का उपयोग करके ओवरहेड से बच सकते हैं, मौजूदा तत्वों को दो बार ढूंढने से बचें। या संग्रह। काउंटर अगर आप अजगर 2.7+ का उपयोग कर रहे हैं।

def increment(map, key): 
    map[key] = map.get(key,0)+1 

Answer 4

पायथन शब्दकोश अत्यधिक अनुकूलित हैं।पायथन विभिन्न विशेष-केस अनुकूलन बनाता है जो पाइथन डेवलपर्स को सीपीथन शब्दकोश कार्यान्वयन में पूरा करते हैं।

1. सीपीथॉन में, सभी PyDictObject को केवल स्ट्रिंग कुंजी वाले शब्दकोशों के लिए अनुकूलित किया गया है।
2. पायथन के शब्दकोश के प्रयास कभी नहीं अधिक से अधिक 2/पूर्ण 3rds होने के लिए बनाता है।

पुस्तक "Beautiful Code" इस पर चर्चा करती है।

अठारहवें अध्याय पायथन के शब्दकोश कार्यान्वयन है: Adrew Kuchling द्वारा सभी लोगों के लिए सब कुछ होने के नाते

यह इसका इस्तेमाल करने से जो करने के लिए इन सभी अनुकूलन को दोहराने के लिए होगा हाथ से गढ़ी गई कस्टम कार्यान्वयन को प्राप्त करने की कोशिश बेहतर है डिक्शनरी लुक अप के मुख्य सीपीथन कार्यान्वयन के पास कहीं भी हो।

Answer 5

एक dict का उपयोग करना हे है (1)। dict विकसित होता है, पुनः आबंटन कभी कभी आवश्यक है, लेकिन है कि हे परिशोधित है (1)

अपने अन्य एल्गोरिथ्म हे (लॉग एन), सरल dict हमेशा इसे हरा के रूप में डाटासेट बड़ा बढ़ता जाएगा।

आप पेड़ के किसी भी प्रकार का उपयोग करते हैं, मैं एक हे (लॉग एन) वहाँ कहीं में घटक उम्मीद करेंगे।

इतना ही नहीं अगर आप सोच रहे हैं जो एक hashtable और एक AVL पेड़ के बीच बेहतर प्रदर्शन किया है के बिंदु पर कर रहे हैं, वहाँ अन्य खिलाड़ियों के बहुत सारे हैं एक हैश तालिका काफी अच्छा है, यह बेहतर है