🔤 🚶🏽 👨🏼‍🍳 CPython (और PyPy) में शब्दकोशों के कुछ अंश ⛳️ 🐾 👶🏼

पायथन में शब्दकोशों की आंतरिक संरचना केवल बाल्टी और निजी हैशिंग तक सीमित नहीं है। यह साझा कुंजियों, हैश कैशिंग, DKIX_DUMMY और त्वरित तुलनाओं की एक अद्भुत दुनिया है, जिसे और भी तेज़ी से (बग की कीमत पर 2 ^ -64 की अनुमानित संभावना के साथ) किया जा सकता है।

यदि आप अपने द्वारा बनाए गए शब्दकोश में तत्वों की संख्या नहीं जानते हैं, तो प्रत्येक तत्व के लिए कितनी मेमोरी खर्च की जाती है, क्यों अब (सीपीथॉन 3.6 इसके बाद) शब्दकोश दो सरणियों में लागू किया गया है और यह कैसे सम्मिलन आदेश को बनाए रखने से संबंधित है, या आप रेमंड हेटिंगर "मॉडर्न पायथन" की प्रस्तुति नहीं देखते हैं। शब्दकोश एक दर्जन महान विचारों का संगम। ” फिर स्वागत है।

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

CPython में शब्दकोश हर जगह हैं, कक्षाएं, वैश्विक चर, kwargs पैरामीटर उन पर आधारित हैं, दुभाषिया हजारों शब्दकोशों बनाता है , भले ही आप स्वयं किसी भी घुंघराले कोष्ठक को अपनी स्क्रिप्ट में नहीं जोड़ते। लेकिन कई लागू समस्याओं को हल करने के लिए, शब्दकोशों का भी उपयोग किया जाता है, यह आश्चर्य की बात नहीं है कि उनके कार्यान्वयन में सुधार जारी है और अधिक से अधिक विभिन्न चाल में बढ़ रहा है।

शब्दकोशों का मूल कार्यान्वयन (हश्माप के माध्यम से)

यदि आप मानक हश्माप और निजी हैशिंग के काम से परिचित हैं, तो आप अगले अध्याय पर जा सकते हैं।

अंतर्निहित शब्दकोष सरल है: यदि हमारे पास एक ऐसा सरणी है जिसमें समान आकार की वस्तुओं को संग्रहीत किया जाता है, तो हम आसानी से वांछित वस्तु तक पहुंच प्राप्त करते हैं, सूचकांक को जानते हुए।

हम केवल ऑब्जेक्ट के आकार से गुणा किए गए इंडेक्स को सरणी के ऑफ़सेट में जोड़ते हैं, और हमें वांछित ऑब्जेक्ट का पता मिलता है।

लेकिन क्या होगा यदि हम एक पूर्णांक अनुक्रमणिका द्वारा नहीं, बल्कि एक अन्य प्रकार के चर द्वारा खोज को व्यवस्थित करना चाहते हैं, उदाहरण के लिए, उपयोगकर्ताओं को उनके मेल पते पर खोजने के लिए?

एक साधारण सरणी के मामले में, हमें सरणी में सभी उपयोगकर्ताओं के मेल के माध्यम से देखना होगा और उनकी खोज के साथ तुलना करनी होगी, इस दृष्टिकोण को रैखिक खोज कहा जाता है और, जाहिर है, यह सूचकांक द्वारा ऑब्जेक्ट तक पहुंचने की तुलना में बहुत धीमा है।

यदि हम उस क्षेत्र के आकार को सीमित करते हैं, जिसमें आप खोज करना चाहते हैं, तो रेखीय खोज में काफी तेजी आ सकती है। यह आमतौर पर हैश के शेष भाग को प्राप्त करके किया जाता है। खोजा गया क्षेत्र प्रमुख है।

नतीजतन, एक रेखीय खोज पूरे बड़े सरणी पर नहीं, बल्कि उसके हिस्से में की जाती है।

लेकिन क्या होगा अगर वहाँ पहले से ही एक तत्व है? यह बहुत अच्छी तरह से हो सकता है, क्योंकि किसी ने भी गारंटी नहीं दी है कि हैश को विभाजित करने वाले अवशेष अद्वितीय होंगे (जैसे हैश ही)। इस स्थिति में, ऑब्जेक्ट को अगले इंडेक्स पर रखा जाएगा, अगर यह व्यस्त है, तो यह एक अन्य इंडेक्स द्वारा शिफ्ट होगा और इसी तरह जब तक यह एक मुफ्त नहीं मिल जाता है। किसी आइटम को पुनर्प्राप्त करते समय, उसी हैश के साथ सभी कुंजियों को देखा जाएगा।

इस प्रकार के हैशिंग को निजी कहा जाता है। यदि शब्दकोश में कुछ मुफ्त कोशिकाएं हैं, तो इस तरह की खोज एक रैखिक एक में पतित होने का खतरा है, इसलिए हम सभी जीत खो देंगे जिसके लिए शब्दकोश बनाया गया था, इससे बचने के लिए दुभाषिया भरा हुआ 1/2 / 2/3 सरणी रखता है। यदि पर्याप्त मुक्त कोशिकाएं नहीं हैं, तो एक नया सरणी पहले वाले से दो गुना बड़ा है, और पुराने से तत्व एक समय में नए में स्थानांतरित हो जाते हैं।

यदि आइटम हटा दिया गया है तो क्या करें? इस स्थिति में, सरणी में एक खाली सेल बनता है और कुंजी द्वारा खोज एल्गोरिथ्म भेद नहीं कर सकता है, यह सेल खाली है क्योंकि इस तरह के हैश वाला एक तत्व शब्दकोश में नहीं था, या क्योंकि इसे हटा दिया गया था। हटाने के दौरान डेटा हानि से बचने के लिए, सेल को एक विशेष ध्वज (DKIX_DUMMY) के साथ चिह्नित किया गया है। यदि तत्व खोज के दौरान इस ध्वज का सामना किया जाता है, तो खोज जारी रहती है, सेल को व्यस्त माना जाता है, अगर डाला जाता है, तो सेल अधिलेखित हो जाएगा।

पायथन में कार्यान्वयन सुविधाएँ

शब्दकोश के प्रत्येक तत्व में लक्ष्य वस्तु और कुंजी का लिंक होना चाहिए। कुंजी को टकराव प्रसंस्करण के लिए संग्रहीत किया जाना चाहिए, वस्तु - स्पष्ट कारणों के लिए। चूंकि कुंजी और ऑब्जेक्ट दोनों किसी भी प्रकार और आकार के हो सकते हैं, हम उन्हें सीधे संरचना में संग्रहीत नहीं कर सकते हैं, वे गतिशील मेमोरी में हैं, और उनके लिए लिंक सूची आइटम की संरचना में संग्रहीत हैं। यही है, एक तत्व का आकार दो पॉइंटर्स के न्यूनतम आकार (64-बिट सिस्टम पर 16 बाइट्स) के बराबर होना चाहिए। हालाँकि, दुभाषिया हैश को भी संग्रहीत करता है, ऐसा इसलिए किया जाता है ताकि शब्दकोश के आकार में प्रत्येक वृद्धि के साथ पुनरावृत्ति न हो। एक नए तरीके से प्रत्येक कुंजी से हैश की गणना करने और बकेट की संख्या से विभाजन के शेष को लेने के बजाय, दुभाषिया केवल पहले से सहेजे गए मूल्य को पढ़ता है। लेकिन, अगर मुख्य वस्तु को बदल दिया जाए तो क्या होगा? इस मामले में, हैश को पुनर्गणना किया जाना चाहिए और संग्रहीत मूल्य गलत होगा? ऐसी स्थिति असंभव है, क्योंकि उत्परिवर्तनीय प्रकार शब्दकोश कुंजी नहीं हो सकते हैं।

शब्दकोश तत्व की संरचना निम्नानुसार परिभाषित की गई है:

typedef struct { Py_hash_t me_hash; //  PyObject *me_key; //    PyObject *me_value; //     } PyDictKeyEntry;

शब्दकोश का न्यूनतम आकार PyDict_MINSIZE निरंतर द्वारा घोषित किया गया है, जो 8. है। डेवलपर्स ने फैसला किया कि यह खाली आकार और सरणी के गतिशील विस्तार के लिए समय संग्रहीत करने के लिए अनावश्यक स्मृति अपव्यय से बचने के लिए इष्टतम आकार है। इस प्रकार, एक शब्दकोश बनाते समय (संस्करण 3.6 तक), आपको शब्दकोश में संरचना में न्यूनतम 8 तत्वों की आवश्यकता होती है * 24 बाइट्स संरचना में = 192 बाइट्स (यह शेष फ़ील्ड को ध्यान में नहीं रखता है: शब्दकोश चर की लागत ही, तत्वों की संख्या का काउंटर, आदि)

कस्टम क्लास फ़ील्ड को लागू करने के लिए भी डिक्शनरी का उपयोग किया जाता है। पायथन आपको गतिशील रूप से विशेषताओं की संख्या को बदलने की अनुमति देता है, इस गतिशीलता को अतिरिक्त लागतों की आवश्यकता नहीं होती है, क्योंकि एक विशेषता को जोड़ना / निकालना अनिवार्य रूप से शब्दकोश पर संबंधित ऑपरेशन के बराबर है। हालाँकि, कार्यक्रमों की एक अल्पसंख्यक इस कार्यक्षमता का उपयोग करते हैं, अधिकांश __in__ में घोषित क्षेत्रों तक सीमित हैं। लेकिन प्रत्येक वस्तु को अपनी कुंजी और हैश के साथ अपने शब्दकोश को संग्रहित करना चाहिए, इस तथ्य के बावजूद कि वे अन्य वस्तुओं के साथ मेल खाते हैं। यहां एक तार्किक सुधार केवल एक ही स्थान पर साझा कुंजी संग्रहीत कर रहा है, जो कि पीईपी 412 - की-शेयरिंग डिक्शनरी में लागू किया गया था। डिक्शनरी को गतिशील रूप से बदलने की क्षमता गायब नहीं हुई: यदि ऑर्डर या कुंजियों की संख्या को बदल दिया जाता है, तो डिक्शनरी को विभाजन कीज़ से नियमित में बदल दिया जाता है।

टकराव से बचने के लिए, शब्दकोश का अधिकतम "लोडिंग" सरणी के वर्तमान आकार का 2/3 है।

 #define USABLE_FRACTION(n) (((n) << 1)/3)

इस प्रकार, पहला विस्तार तब होगा जब 6 वें तत्व को जोड़ा जाएगा।

सरणी काफी छुट्टी दे दी जाती है, कार्यक्रम के संचालन के दौरान, आधे से एक तिहाई कोशिकाएं खाली रहती हैं, जिससे मेमोरी की खपत बढ़ जाती है। इस सीमा को दरकिनार करने के लिए और, यदि संभव हो तो, केवल आवश्यक डेटा संग्रहीत करें, सरणी ~~अमूर्त~~ का एक नया ~~स्तर~~ जोड़ा गया था।

उदाहरण के लिए, एक विरल सरणी के भंडारण के बजाय:

  d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'} # -> entries = [['--', '--', '--'], [-8522787127447073495, 'barry', 'green'], ['--', '--', '--'], ['--', '--', '--'], ['--', '--', '--'], [-9092791511155847987, 'timmy', 'red'], ['--', '--', '--'], [-6480567542315338377, 'guido', 'blue']]

संस्करण 3.6 से शुरू होकर, शब्दकोशों का आयोजन इस प्रकार है:

  indices = [None, 1, None, None, None, 0, None, 2] entries = [[-9092791511155847987, 'timmy', 'red'], [-8522787127447073495, 'barry', 'green'], [-6480567542315338377, 'guido', 'blue']]

यानी केवल वे रिकॉर्ड जो वास्तव में आवश्यक हैं, संग्रहीत किए जाते हैं, उन्हें हैश तालिका से अलग सरणी में निकाल दिया जाता है, और संबंधित रिकॉर्ड के केवल अनुक्रमित को हैश तालिका में संग्रहीत किया जाता है। यदि शुरू में सरणी 192 बाइट्स लेती थी, तो अब यह केवल 80 (3 * 24-बाइट्स प्रत्येक रिकॉर्ड के लिए + 8 बाइट्स इंडिकेट के लिए) है। 58% पर संपीड़न हासिल किया। [२]

सूचकांकों में एक तत्व का आकार भी गतिशील रूप से बदलता है, शुरू में यह एक बाइट के बराबर होता है, अर्थात, पूरे सरणी को एक रजिस्टर में रखा जा सकता है, जब सूचकांक 8 बिट में फिट होना शुरू होता है, तो तत्व 16 तक विस्तारित होते हैं, फिर 32 बिट तक। खाली और हटाई गई वस्तुओं के लिए विशेष स्थिरांक DKIX_EMPTY और DKIX_DUMMY हैं, क्रमशः 16 बाइट्स में सूचकांक विस्तार तब होता है जब शब्दकोश में 127 से अधिक आइटम होते हैं।

नई वस्तुओं को प्रविष्टियों में जोड़ा जाता है, अर्थात्, जब शब्दकोश का विस्तार होता है, तो उन्हें स्थानांतरित करने की कोई आवश्यकता नहीं होती है, आपको केवल सूचकांकों के आकार को बढ़ाने और इसे इंडेक्स के साथ ओवरफिल करने की आवश्यकता होती है।

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

CPython Developers को यह कार्यान्वयन इतना पसंद आया कि विनिर्देश द्वारा प्रविष्टि क्रम बनाए रखने के लिए अब शब्दकोशों की आवश्यकता है। यदि पहले शब्दकोशों का क्रम निर्धारित किया गया था, अर्थात यह कड़ाई से एक हैश द्वारा परिभाषित किया गया था और शुरू से शुरू होने तक अपरिवर्तित था, फिर इसमें थोड़ी यादृच्छिकता जोड़ दी गई ताकि चाबियाँ हर बार अलग हो जाएं, अब आदेश को संरक्षित करने के लिए शब्दकोश कुंजियों की आवश्यकता होती है। यह कितना आवश्यक था, और क्या करना है अगर शब्दकोश का एक और भी अधिक प्रभावी कार्यान्वयन प्रकट होता है, लेकिन सम्मिलन क्रम को संरक्षित नहीं करता है, यह स्पष्ट नहीं है।

हालांकि, कक्षाओं और kwargs में विशेषताओं की घोषणा को संरक्षित करने के लिए एक तंत्र को लागू करने का अनुरोध किया गया था, और यह कार्यान्वयन आपको विशेष तंत्र के बिना इन समस्याओं को बंद करने की अनुमति देता है।

सीपीयथॉन कोड में यह कैसा दिखता है:

 struct _dictkeysobject { Py_ssize_t dk_refcnt; /* Size of the hash table (dk_indices). It must be a power of 2. */ Py_ssize_t dk_size; /* Function to lookup in the hash table (dk_indices): - lookdict(): general-purpose, and may return DKIX_ERROR if (and only if) a comparison raises an exception. - lookdict_unicode(): specialized to Unicode string keys, comparison of which can never raise an exception; that function can never return DKIX_ERROR. - lookdict_unicode_nodummy(): similar to lookdict_unicode() but further specialized for Unicode string keys that cannot be the <dummy> value. - lookdict_split(): Version of lookdict() for split tables. */ dict_lookup_func dk_lookup; /* Number of usable entries in dk_entries. */ Py_ssize_t dk_usable; /* Number of used entries in dk_entries. */ Py_ssize_t dk_nentries; /* Actual hash table of dk_size entries. It holds indices in dk_entries, or DKIX_EMPTY(-1) or DKIX_DUMMY(-2). Indices must be: 0 <= indice < USABLE_FRACTION(dk_size). The size in bytes of an indice depends on dk_size: - 1 byte if dk_size <= 0xff (char*) - 2 bytes if dk_size <= 0xffff (int16_t*) - 4 bytes if dk_size <= 0xffffffff (int32_t*) - 8 bytes otherwise (int64_t*) Dynamically sized, SIZEOF_VOID_P is minimum. */ char dk_indices[]; /* char is required to avoid strict aliasing. */ /* "PyDictKeyEntry dk_entries[dk_usable];" array follows: see the DK_ENTRIES() macro */ };

लेकिन पुनरावृति अधिक जटिल है जितना आप शुरू में सोच सकते हैं, अतिरिक्त सत्यापन तंत्र हैं कि पुनरावृत्ति के दौरान शब्दकोश नहीं बदला गया था, उनमें से एक शब्दकोश का 64-बिट संस्करण है जो प्रत्येक शब्दकोश को संग्रहीत करता है।

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

  >>>[hash(i) for i in range(4)] [0, 1, 2, 3]

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

  //   i = i + 1 % n //   : #define PERTURB_SHIFT 5 perturb >>= PERTURB_SHIFT; j = (5*j) + 1 + perturb; //   j % n

perturb एक पूर्णांक चर हैश द्वारा आरंभ किया गया है। यह ध्यान दिया जाना चाहिए कि बड़ी संख्या में टकराव की स्थिति में, यह रीसेट हो जाता है और निम्न सूचकांक की गणना सूत्र द्वारा की जाती है:

  j = (5 * j + 1) % n

शब्दकोश से एक तत्व निकालते समय, एक ही खोज की जाती है: जिस स्लॉट में तत्व स्थित होना चाहिए, उसके सूचकांक की गणना की जाती है, यदि स्लॉट खाली है, तो अपवाद "मूल्य नहीं मिला" फेंक दिया गया है। यदि इस स्लॉट में कोई मूल्य है, तो आपको यह जांचने की आवश्यकता है कि इसकी कुंजी उसी से मेल खाती है जिसे आप खोज रहे हैं, यदि टक्कर होती है तो यह संभव नहीं हो सकता है। हालाँकि, कुंजी लगभग किसी भी ऑब्जेक्ट की हो सकती है, जिसमें से एक जिसके लिए तुलना ऑपरेशन में काफी समय लगता है। एक तुलनात्मक ऑपरेशन से बचने के लिए, पायथन में कई तरकीबें इस्तेमाल की जाती हैं:

  #   (   ,  C) def eq(key, entity): if id(key) == id(entity): return True if hash(key) != hash(entity): return False return key == entity

सबसे पहले, पॉइंटर्स की तुलना की जाती है, यदि वांछित ऑब्जेक्ट का कुंजी पॉइंटर उस ऑब्जेक्ट के पॉइंटर के बराबर है जिसे खोजा जा रहा है, अर्थात, वे एक ही मेमोरी क्षेत्र की ओर इशारा करते हैं, तो तुलना तुरंत सच हो जाती है। लेकिन यह सब नहीं है। जैसा कि आप जानते हैं, समान वस्तुओं में समान हैश होना चाहिए, जिसका अर्थ है कि अलग-अलग हैश वाली वस्तुएँ समान नहीं हैं। बिंदुओं की जांच करने के बाद, हैश की जांच की जाती है; यदि वे समान नहीं हैं, तो झूठे को वापस कर दिया जाएगा। और केवल अगर हैश बराबर हैं, तो एक ईमानदार तुलना कहा जाएगा।

इस तरह के परिणाम की संभावना क्या है? लगभग 2 ^ -64, बेशक, हैश मूल्य की आसान भविष्यवाणी के कारण, आप आसानी से इस तरह के उदाहरण को उठा सकते हैं, लेकिन वास्तव में, यह सत्यापन अक्सर कितना नहीं आता है? रेमंड हेटिंगर ने अंतिम तुलना ऑपरेशन को एक साधारण रिटर्न सच के साथ बदलकर दुभाषिया को इकट्ठा किया। यानी अगर उनके हैश बराबर हैं तो दुभाषिया वस्तुओं को बराबर समझता है। फिर उन्होंने इस दुभाषिए पर कई लोकप्रिय परियोजनाओं के स्वचालित परीक्षण किए, जो सफलतापूर्वक समाप्त हो गए। यह समान हैश वाली वस्तुओं पर समान रूप से विचार करने के लिए अजीब लग सकता है, इसके अतिरिक्त उनकी सामग्री की जांच करने के लिए नहीं, और केवल हैश पर पूरी तरह से भरोसा करते हैं, लेकिन आप इसे नियमित रूप से गिट या टोरेंट प्रोटोकॉल का उपयोग करते समय करते हैं। वे फाइलों (फाइल ब्लॉक्स) को समान मानते हैं यदि उनकी हैश बराबर होती है, जो अच्छी तरह से त्रुटियों को जन्म दे सकती है, लेकिन उनके निर्माता (और हम सभी) आशा करते हैं कि यह बिना किसी कारण के ध्यान देने योग्य है, टक्कर की संभावना बहुत छोटी है।

अब आपको अंततः शब्दकोश की संरचना को समझना चाहिए, जो इस तरह दिखता है:

 typedef struct { PyObject_HEAD /* Number of items in the dictionary */ Py_ssize_t ma_used; /* Dictionary version: globally unique, value change each time the dictionary is modified */ uint64_t ma_version_tag; PyDictKeysObject *ma_keys; /* If ma_values is NULL, the table is "combined": keys and values are stored in ma_keys. If ma_values is not NULL, the table is splitted: keys are stored in ma_keys and values are stored in ma_values */ PyObject **ma_values; } PyDictObject;

भविष्य बदलता है

पिछले अध्याय में, हमने माना कि क्या पहले से ही लागू किया गया है और सभी को उनके काम में इस्तेमाल किया जा सकता है, लेकिन सुधार निश्चित रूप से सीमित नहीं हैं: संस्करण 3.8 की योजनाओं में उल्टे शब्दकोशों के लिए समर्थन शामिल है। दरअसल, कुछ भी नहीं है तत्वों की एक सरणी की शुरुआत से परेशान करने और सूचकांकों को बढ़ाने के बजाय, अंत से शुरू करने और सूचकांकों को कम करने से रोकता है।

अतिरिक्त सामग्री

विषय में गहन विसर्जन के लिए, निम्नलिखित सामग्रियों से खुद को परिचित करने की सिफारिश की जाती है:

लेख की शुरुआत में रिपोर्ट का रिकॉर्ड
शब्दकोशों के नए कार्यान्वयन के लिए प्रस्ताव
सीपीथॉन में डिक्शनरी सोर्स कोड

CPython (और PyPy) में शब्दकोशों के कुछ अंश

शब्दकोशों का मूल कार्यान्वयन (हश्माप के माध्यम से)

पायथन में कार्यान्वयन सुविधाएँ

भविष्य बदलता है

अतिरिक्त सामग्री

More articles: