हैश ऐरे मैप्ड ट्रिए

From Vigyanwiki
Revision as of 19:34, 10 July 2023 by alpha>Indicwiki (Created page with "{{Technical|date=October 2019}} एक हैश सरणी मैप किया गया प्रयास<ref name="bagwell" />(एचएएमटी) एक सा...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

एक हैश सरणी मैप किया गया प्रयास[1](एचएएमटी) एक साहचर्य सरणी का कार्यान्वयन है जो हैश तालिका और सरणी मैप किया गया प्रयास की विशेषताओं को जोड़ता है।[1] यह हैश ट्री (लगातार डेटा संरचना) की अधिक सामान्य धारणा का एक परिष्कृत संस्करण है।

ऑपरेशन

एचएएमटी एक सरणी मैप्ड ट्राइ है जहां चाबियों का समान वितरण और निरंतर कुंजी लंबाई सुनिश्चित करने के लिए चाबियों को पहले हैश किया जाता है।

एचएएमटी के एरे मैप्ड ट्राइ के एक विशिष्ट कार्यान्वयन में, प्रत्येक नोड में कुछ निश्चित संख्या एन स्लॉट के साथ एक तालिका होती है, जिसमें प्रत्येक स्लॉट में एक शून्य पॉइंटर या दूसरे नोड के लिए एक पॉइंटर होता है। एन आमतौर पर 32 है। चूंकि प्रत्येक नोड के लिए एन पॉइंटर्स के लिए स्थान आवंटित करना महंगा होगा, इसके बजाय प्रत्येक नोड में एक बिटमैप होता है जो एन बिट लंबा होता है जहां प्रत्येक बिट एक गैर-शून्य पॉइंटर की उपस्थिति को इंगित करता है। इसके बाद बिटमैप (इसका हथौड़ा चलाना वजन) में पॉइंटर्स की संख्या के बराबर लंबाई वाले पॉइंटर्स की एक सरणी होती है।

एचएएमटी के लाभ

हैश ऐरे मैप्ड ट्राई मेमोरी का अधिक किफायती उपयोग करते हुए लगभग हैश टेबल जैसी गति प्राप्त करता है। साथ ही, हैश तालिका का समय-समय पर आकार बदलना पड़ सकता है, जो एक महंगा ऑपरेशन है, जबकि HAMT गतिशील रूप से बढ़ते हैं। आम तौर पर, एचएएमटी प्रदर्शन में कुछ एन स्लॉट्स के साथ एक बड़ी रूट टेबल द्वारा सुधार किया जाता है; कुछ एचएएमटी प्रकार जड़ को धीरे-धीरे बढ़ने देते हैं[1]प्रदर्शन पर नगण्य प्रभाव के साथ.

कार्यान्वयन विवरण

एचएएमटी के कार्यान्वयन में हैमिंग वेट फ़ंक्शन का उपयोग शामिल है, जो किसी संख्या के बाइनरी प्रतिनिधित्व में इकाइयों की संख्या की गणना करता है। यह ऑपरेशन हैमिंग वेट#प्रोसेसर समर्थन में उपलब्ध है, लेकिन यह हैमिंग वेट#भाषा समर्थन|केवल कुछ उच्च-स्तरीय भाषाओं में उपलब्ध है। हालाँकि जनसंख्या गणना को हैमिंग वेट#कुशल कार्यान्वयन का उपयोग करके बिग-ओ संकेतन |ओ(1) समय में सॉफ़्टवेयर में लागू किया जा सकता है, ऐसा करने से ऑपरेशन परिमाण के क्रम में धीमा हो सकता है।[citation needed]

कार्यान्वयन

प्रोग्रामिंग भाषाएँ क्लोजर,[2] स्काला (प्रोग्रामिंग भाषा), और फ़्रीज (प्रोग्रामिंग भाषा)[3] अपने मूल हैश मैप प्रकार के लिए हैश सरणी मैप किए गए प्रयासों के लगातार डेटा संरचना संस्करण का उपयोग करें। हास्केल (प्रोग्रामिंग भाषा) लाइब्रेरी अनऑर्डर्ड-कंटेनर लगातार मानचित्र को लागू करने और डेटा संरचनाओं को सेट करने के लिए इसका उपयोग करती है।[4] एक अन्य हास्केल लाइब्रेरी एसटीएम-कंटेनर सॉफ़्टवेयर ट्रांसेक्शनल मेमोरी के संदर्भ में उपयोग के लिए एल्गोरिदम को अनुकूलित करता है।[5] एक जावास्क्रिप्ट एचएएमटी लाइब्रेरी [6] क्लोजर कार्यान्वयन पर आधारित भी उपलब्ध है। माणिक [7] रूबी (प्रोग्रामिंग भाषा) के कार्यान्वयन में एक HAMT शामिल है, जो ज्यादातर रूबी में लिखा गया है लेकिन 3 के साथ[8] आदिम। एर्लैंग (प्रोग्रामिंग भाषा) में बड़े मानचित्र रिलीज़ 18.0 के बाद से आंतरिक रूप से एक पर्सिस्टेंट डेटा संरचना HAMT प्रतिनिधित्व का उपयोग करते हैं।[9] पोनी प्रोग्रामिंग भाषा अपने सतत संग्रह पैकेज में हैश मैप के लिए HAMT का उपयोग करती है।[10] आईएम और आईएम-आरसी क्रेट्स, जो रस्ट प्रोग्रामिंग भाषा के लिए लगातार संग्रह प्रकार प्रदान करते हैं, अपने लगातार हैश टेबल और हैश सेट के लिए एचएएमटी का उपयोग करते हैं। [11] समवर्ती लॉक-मुक्त संस्करण[12] Ctrie नामक हैश ट्राइ एक परिवर्तनीय थ्रेड-सुरक्षित कार्यान्वयन है जो प्रगति सुनिश्चित करता है। डेटा-संरचना सही साबित हुई है[13] - Ctrie ऑपरेशंस में परमाणुता (प्रोग्रामिंग) , रैखिकता और ताला मुक्त |लॉक-फ्रीडम गुण दिखाए गए हैं।

यह भी देखें

संदर्भ

  1. ↑ 1.0 1.1 1.2 Phil Bagwell (2000). Ideal Hash Trees (PDF) (Report). Infoscience Department, École Polytechnique Fédérale de Lausanne.
  2. ↑ "clojure/clojure". GitHub. 8 December 2022.
  3. ↑ "Frege/frege". GitHub. 7 December 2022.
  4. ↑ Johan Tibell, A. Announcing unordered-containers 0.2
  5. ↑ Nikita Volkov, Announcing the "stm-containers" library, 2014
  6. ↑ "mattbierner/hamt". GitHub. 27 November 2022.
  7. ↑ "रुबिनियस के HAMT की रूबी स्रोत फ़ाइल". GitHub.
  8. ↑ https://github.com/rubinius/rubinius/blob/master/machine/builtin/system.cpp#L1724-L1802[dead link]
  9. ↑ "Erlang Programming Language".
  10. ↑ "horse: Pony is an open-source, actor-model, capabilities-secure, high performance programming language: Ponylang/ponyc". GitHub. 2018-11-26.
  11. ↑ "API docs for Rust im-rc crate".
  12. ↑ Prokopec, A. Implementation of Concurrent Hash Tries on GitHub
  13. ↑ Prokopec, A. et al. (2011) Cache-Aware Lock-Free Concurrent Hash Tries. Technical Report, 2011.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=हैश_ऐरे_मैप्ड_ट्रिए&oldid=227415’