🦋 👎🏽 👩🏿‍💼 पायथन में शब्दकोश कार्यान्वयन 👩🏼‍✈️ 🙊 🤱🏻

सभी को नमस्कार, 30 अप्रैल को, अल्गोरिद्म फॉर डेवलपर्स कोर्स ओटीयूएस में शुरू होगा, और यही वह है जो आज की सामग्री के प्रकाशन के लिए समर्पित है। चलिए शुरू करते हैं।

इस लेख में, आप सीखेंगे कि पायथन में शब्दकोशों को कैसे लागू किया जाता है।
शब्दकोशों को कुंजी का उपयोग करके अनुक्रमित किया जाता है, और उन्हें संबंधित सरणियों के रूप में माना जा सकता है। आइए शब्दकोश में 3 मुख्य / मूल्य जोड़े जोड़ें:

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

मानों को निम्नानुसार पहुँचा जा सकता है:

 >>> d['a'] 1 >>> d['b'] 2 >>> d['c'] 3 >>> d['d'] Traceback (most recent call last): File "<stdin>", line 1, in <module> KeyError: 'd'

कुंजी “d” मौजूद नहीं है, इसलिए KeyError त्रुटि होगी।

हैश टेबल

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

 >>> map(hash, (0, 1, 2, 3)) [0, 1, 2, 3] >>> map(hash, ("namea", "nameb", "namec", "named")) [-1658398457, -1658398460, -1658398459, -1658398462]

हम मानेंगे कि इस लेख के अंत तक हम स्ट्रिंग्स का उपयोग कुंजियों के रूप में करेंगे। स्ट्रिंग के लिए पायथन में हैश फ़ंक्शन निम्नानुसार परिभाषित किया गया है:

 arguments: string object returns: hash function string_hash: if hash cached: return it set len to string's length initialize var p pointing to 1st char of string object set x to value pointed by p left shifted by 7 bits while len >= 0: set var x to (1000003 * x) xor value pointed by p increment pointer p set x to x xor length of string object cache x as the hash so we don't need to calculate it again return x as the hash

यदि आप पायथन में hash('a') को 12416037344 string_hash() , तो यह string_hash() 12416037344 करेगा और 12416037344 वापस 12416037344 । यहां हम डिफ़ॉल्ट रूप से 64-बिट मशीन का उपयोग करते हैं।

यदि मान / कुंजी युग्मों को संग्रहीत करने के लिए आकार की एक सरणी का उपयोग किया जाता है, तो सरणी में सेल के सेल के सूचकांक की गणना करने के लिए एक मुखौटा का उपयोग किया जाएगा, जिसे -1 रूप में गणना की जाती है। यह दृष्टिकोण सेल सूचकांकों की त्वरित गणना करता है। आकार बदलने वाले तंत्र के कारण एक खाली सेल मिलने की संभावना काफी अधिक है, जो नीचे वर्णित है। इसका मतलब यह है कि एक साधारण गणना ज्यादातर मामलों में समझ में आता है। सरणी का आकार 8 है, 'a' का सूचकांक होगा: hash('a') & 7 = 0 । 'b' लिए इंडेक्स 2 है, 'c' लिए इंडेक्स 3 है, 'z' लिए इंडेक्स 3 है, जैसे 'b' , और यहीं पर हमें टक्कर मिलती है।

जैसा कि हम देख सकते हैं, कि पायथन क्रमिक होने पर, पायथन में एक हैश फंक्शन अपने काम को एक गुणवत्तापूर्ण तरीके से करता है, जो अच्छा है, क्योंकि आपको अक्सर ऐसे डेटा के साथ काम करना पड़ता है। हालाँकि, जैसे ही हम 'z' कुंजी जोड़ते हैं, एक टकराव होता है क्योंकि यह पिछले वाले के अनुरूप नहीं होता है।

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

खुला पता

ओपन एड्रेसिंग एक टक्कर रिज़ॉल्यूशन तकनीक है जो प्रोबिंग का उपयोग करती है। 'z' के मामले में, सेल 3 का सूचकांक पहले से ही सरणी में उपयोग किया जाता है, इसलिए हमें दूसरे सूचकांक की तलाश करनी होगी जो अभी तक उपयोग नहीं किया गया है। एक कुंजी / मूल्य जोड़ी को जोड़ने का संचालन औसत ओ (1) पर होता है, साथ ही साथ खोज ऑपरेशन भी।

मुक्त कोशिकाओं की खोज के लिए, एक द्विघात जांच क्रम का उपयोग किया जाता है। इसे निम्नानुसार लागू किया जाता है:

 j = (5*j) + 1 + perturb; perturb >>= PERTURB_SHIFT; use j % 2**i as the next table index;

(5 * j) +1 पर होने वाली पुनरावृत्ति बिट्स में बड़े अंतर को बढ़ाती है जो मूल सूचकांक को प्रभावित नहीं करती है। इस मामले में चर "perturb" हैश कोड के अन्य बिट्स में लेता है।

आइए हम जिज्ञासा से बाहर देखें कि क्या होता है यदि हमारे पास तालिका आकार 32 और j = 3 के साथ एक नमूना अनुक्रम है।

3 -> 11 -> 19 -> 29 -> 5 -> 6 -> 16 -> 31 -> 28 -> 13 -> 2 ...

आप स्रोत कोड के लिए डिक्टोबोजेक्ट सी.क्यू का हवाला देकर इस जांच क्रम के बारे में अधिक जान सकते हैं। फ़ाइल के शीर्ष पर जांच तंत्र का विस्तृत विवरण पाया जा सकता है।

आइए इस उदाहरण के साथ पायथन स्रोत कोड देखें।

सी शब्दकोश संरचनाओं

निम्नलिखित सी संरचना का उपयोग शब्दकोश में प्रविष्टि को संग्रहीत करने के लिए किया जाता है: कुंजी / मूल्य जोड़ी। हैश, कुंजी और मूल्य संग्रहीत हैं। PyObject Python में ऑब्जेक्ट्स के लिए बेस क्लास है।

 typedef struct { Py_ssize_t me_hash; PyObject *me_key; PyObject *me_value; } PyDictEntry;

निम्नलिखित संरचना एक शब्दकोश है। ma_fill प्रयुक्त और निष्क्रिय कोशिकाओं की कुल संख्या है। जब कोई कुंजी जोड़ी हटा दी जाती है तो एक सेल निष्क्रिय माना जाता है। ma_used प्रयुक्त (सक्रिय) कोशिकाओं की संख्या है। ma_mask -1 सरणी के आकार के बराबर है और इसका उपयोग सेल इंडेक्स की गणना के लिए किया जाता है। ma_table एक सरणी है, और ma_smalltable आकार 8 का मूल सरणी है।

 typedef struct _dictobject PyDictObject; struct _dictobject { PyObject_HEAD Py_ssize_t ma_fill; Py_ssize_t ma_used; Py_ssize_t ma_mask; PyDictEntry *ma_table; PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash); PyDictEntry ma_smalltable[PyDict_MINSIZE]; };

शब्दावली प्रारंभिक

जब आप सिर्फ एक शब्दकोश बनाते हैं, तो PyDict_New() फ़ंक्शन PyDict_New() । मैंने कुछ पंक्तियों को हटा दिया और प्रमुख अवधारणाओं पर ध्यान केंद्रित करने के लिए सी कोड को छद्म कोड में बदल दिया।

PyDict_New() फ़ंक्शन:

शब्दकोश वस्तु लौटाता है;
एक नई शब्दकोश वस्तु आवंटित करता है;
शब्दकोश तालिका साफ करता है;
प्रयुक्त शब्दकोश कोशिकाओं और अप्रयुक्त कोशिकाओं ( ma_fill ) की संख्या को 0 पर सेट करता है;
सक्रिय कोशिकाओं ( ma_used ) की संख्या को 0 पर सेट करता है;
डिक्शनरी मास्क ( ma_value ) को डिक्शनरी के आकार के बराबर मान - 1 = 7;
शब्दकोश खोज फ़ंक्शन सेट करता है lookdict_string ;
आवंटित शब्दकोश वस्तु लौटाता है।

आइटम जोड़ें

जब कोई नया कुंजी / मान जोड़ा जाता है, तो PyDict_SetItem() कहा जाता है। यह फ़ंक्शन एक डिक्शनरी को एक सूचक वस्तु और एक इनपुट के रूप में एक कुंजी / मान युग्म को स्वीकार करता है। यह जांचता है कि क्या कुंजी एक स्ट्रिंग है और हैश का मूल्यांकन करता है या कैश्ड का पुन: उपयोग करता है यदि कोई मौजूद है। insertdict() को एक नई कुंजी / मूल्य जोड़ी को जोड़ने के लिए कहा जाता है और शब्दकोश आकार बदल जाता है यदि उपयोग की गई और अप्रयुक्त कोशिकाओं की संख्या सरणी के आकार के 2/3 से अधिक है।

क्यों वास्तव में 2/3? यह सुनिश्चित करने के लिए आवश्यक है कि जांच अनुक्रम मुक्त कोशिकाओं को जल्दी से पर्याप्त पा सके। बाद में हम आकार बदलने के लिए कार्य पर विचार करेंगे।

 arguments: dictionary, key, value returns: 0 if OK or -1 function PyDict_SetItem: if key's hash cached: use hash else: calculate hash call insertdict with dictionary object, key, hash and value if key/value pair added successfully and capacity over 2/3: call dictresize to resize dictionary's table

inserdict() एक नि: शुल्क सेल को खोजने के लिए lookdict_string() खोज फ़ंक्शन का उपयोग करता है। कुंजी को खोजने के लिए उसी फ़ंक्शन का उपयोग किया जाता है।

lookdict_string() हैश और मास्क मानों का उपयोग करके सेल इंडेक्स की गणना करता है। यदि वह सेल इंडेक्स = हैश एंड मास्क (स्लॉट इंडेक्स = हैश एंड मास्क) के मूल्य से कुंजी नहीं ढूंढ सकता है, तो वह ऊपर वर्णित चक्र का उपयोग करना शुरू कर देता है जब तक कि वह एक मुफ्त सेल नहीं पाता। जांच के पहले प्रयास में, यदि कुंजी null , तो पहली खोज के दौरान यह अप्रयुक्त सेल देता है। यह पहले से हटाई गई कोशिकाओं के पुन: उपयोग के लिए प्राथमिकता सुनिश्चित करता है।
हम निम्नलिखित कुंजी / मूल्य जोड़े जोड़ना चाहते हैं: {'a': 1, 'b': 2′, 'z': 26, 'y': 25, 'c': 5, 'x': 24} । यहाँ क्या होगा:

शब्दकोश संरचना 8 के तालिका आकार के साथ आवंटित की गई है।

PyDict_SetItem: key = 'a', value = 1
- हैश = हैश ('ए') = 12416037344
- insertdict
  - lookdict_string
    - स्लॉट इंडेक्स = हैश और मास्क = 12416037344 और 7 = 0
    - स्लॉट 0 का उपयोग नहीं किया गया है, इस सेल को लौटाएं
  - इंडेक्स 0 में कुंजी, मान और हैश के साथ प्रविष्टि का आरंभ
  - ma_used = 1, ma_fill = 1
PyDict_SetItem: कुंजी = 'b', मान = 2
- हैश = हैश ('बी') = 12544037731
- insertdict
  - lookdict_string
    - स्लॉट इंडेक्स = हैश और मास्क = 12544037731 और 7 = 3
    - स्लॉट 3 का उपयोग नहीं किया गया है, इस सेल को लौटाएं
  - इंडेक्स 3 में कुंजी, मूल्य और हैश के साथ प्रविष्टि का आरंभ
  - ma_used = 2, ma_fill = 2
PyDict_SetItem: कुंजी = 'z', मान = 26
- हैश = हैश ('z') = 15616046971
- insertdict
  - lookdict_string
    - स्लॉट इंडेक्स = हैश और मास्क = 15616046971 और 7 = 3
    - स्लॉट 3 का उपयोग किया जाता है, दूसरे सेल का प्रयास करें: 5 मुफ़्त है
    इंडेक्स 5 में कुंजी, मूल्य और हैश के साथ प्रविष्टि का आरंभ
    ma_used = 3, ma_fill = 3
PyDict_SetItem: कुंजी = 'y', मान = 25
- हैश = हैश ('y') = 15488046584
- insertdict
  - lookdict_string
    - स्लॉट इंडेक्स = हैश और मास्क = 15488046584 और 7 = 0
    - स्लॉट 0 का उपयोग किया जाता है, दूसरे सेल का प्रयास करें: 1 मुफ़्त है
  - इंडेक्स 1 में कुंजी, मूल्य और हैश के साथ प्रविष्टि का आरंभ
  - ma_used = 4, ma_fill = 4

PyDict_SetItem: key = 'c', value = 3

हैश = हैश ('c') = 12672038114
insertdict
- lookdict_string
  - स्लॉट इंडेक्स = हैश और मास्क = 12672038114 और 7 = 2
  - स्लॉट 2 का उपयोग नहीं किया गया है, इस सेल को लौटाएं
- इंडेक्स 2 में कुंजी, मूल्य और हैश के साथ प्रविष्टि का आरंभ
- ma_used = 5, ma_fill = 5

PyDict_SetItem: कुंजी = 'x', मान = 24

हैश = हैश ('x') = 15360046201
insertdict
- lookdict_string
  - स्लॉट इंडेक्स = हैश और मास्क = 15360046201 और 7 = 1
  - स्लॉट 1 का उपयोग किया जाता है, दूसरे सेल का प्रयास करें: 7 मुफ़्त है
- इंडेक्स 7 में कुंजी, मूल्य और हैश के साथ प्रविष्टि का आरंभ
- ma_used = 6, ma_fill = 6

यहाँ हम क्या मिलता है:

अब 8 में से 6 कोशिकाओं का उपयोग किया जाता है, सरणी क्षमता के 2/3 से अधिक पर कब्जा कर लिया जाता है। एक बड़ा सरणी आवंटित करने के लिए dictresize() कहा जाता है। यह फ़ंक्शन पुराने तालिका से नए तक के रिकॉर्ड की भी प्रतिलिपि बनाता है।

हमारे मामले में dictresize () को minused = 24 के साथ बुलाया जाता है, जहाँ 4 * ma_used । 2 * ma_used उपयोग तब किया जाता है जब उपयोग की जाने वाली कोशिकाओं की संख्या बहुत बड़ी होती है (50,000 से अधिक)। क्यों 4 गुना अधिक कोशिकाएं हैं? यह आकार बदलने को लागू करने और विरलता को बढ़ाने के लिए कदमों की संख्या को कम करता है।

तालिका का नया आकार 24 से अधिक होना चाहिए, इसकी गणना वर्तमान आकार को 1 बिट से बाईं ओर तब तक स्थानांतरित किया जाता है जब तक कि तालिका का आकार 24 से अधिक नहीं हो जाता है। परिणामस्वरूप, यह 32 होगा, उदाहरण के लिए, 8 -> 16 - 32।

आकार बदलने के दौरान हमारी तालिका के साथ क्या होता है: आकार 32 की एक नई तालिका पर प्रकाश डाला गया है। पुरानी तालिका प्रविष्टियों को 31 के नए मुखौटा मूल्य का उपयोग करके नई तालिका में डाला गया है। परिणाम निम्न है:

आइटम हटाएं

PyDict_DelItem() रिकॉर्ड्स को हटाने के लिए कहा जाता है। हैश की गणना रिकॉर्ड कुंजी के लिए की जाती है, फिर रिकॉर्ड वापस करने के लिए खोज फ़ंक्शन को कहा जाता है। अब सेल खाली है।

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

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

यह प्रकाशन समाप्त हो गया है, और हम परंपरागत रूप से आपकी टिप्पणियों की प्रतीक्षा करते हैं और सभी को एक खुले पाठ के लिए आमंत्रित करते हैं, जो 18 अप्रैल को आयोजित किया जाएगा।

पायथन में शब्दकोश कार्यान्वयन

More articles: