हैश ऐरे मैप्ड ट्रिए: Difference between revisions

From Vigyanwiki
(Created page with "{{Technical|date=October 2019}} एक हैश सरणी मैप किया गया प्रयास<ref name="bagwell" />(एचएएमटी) एक सा...")
 
(text)
Line 1: Line 1:
{{Technical|date=October 2019}}
{{Technical|date=October 2019}}
एक हैश सरणी मैप किया गया प्रयास<ref name="bagwell" />(एचएएमटी) एक [[साहचर्य सरणी]] का कार्यान्वयन है जो [[ हैश तालिका ]] और [[सरणी मैप किया गया प्रयास]] की विशेषताओं को जोड़ता है।<ref name="bagwell">{{cite report
एक '''हैश सरणी मानचित्रित ट्री''' <ref name="bagwell" />(एचएएमटी) एक [[साहचर्य सरणी]] का कार्यान्वयन है जो [[ हैश तालिका |हैश तालिका]] और [[सरणी मैप किया गया प्रयास|हैश सरणी मानचित्रित ट्री]] की विशेषताओं को जोड़ता है। <ref name="bagwell">{{cite report
|title=Ideal Hash Trees
|title=Ideal Hash Trees
|author=Phil Bagwell
|author=Phil Bagwell
Line 7: Line 7:
|url=http://infoscience.epfl.ch/record/64398/files/idealhashtrees.pdf
|url=http://infoscience.epfl.ch/record/64398/files/idealhashtrees.pdf
|year=2000
|year=2000
}}</ref>
}}</ref> यह [[हैश ट्री (लगातार डेटा संरचना)]] की अधिक सामान्य धारणा का एक परिष्कृत संस्करण है।
यह [[हैश ट्री (लगातार डेटा संरचना)]] की अधिक सामान्य धारणा का एक परिष्कृत संस्करण है।


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


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


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


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


== कार्यान्वयन ==
== कार्यान्वयन ==
प्रोग्रामिंग भाषाएँ [[क्लोजर]],<ref>{{cite web|url=https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentHashMap.java|title=clojure/clojure|website=GitHub|date=8 December 2022 }}</ref> [[स्काला (प्रोग्रामिंग भाषा)]], और [[फ़्रीज (प्रोग्रामिंग भाषा)]]<ref>{{cite web|url=https://github.com/Frege/frege/blob/master/frege/data/HashMap.fr|title=Frege/frege|website=GitHub|date=7 December 2022 }}</ref> अपने मूल हैश मैप प्रकार के लिए हैश सरणी मैप किए गए प्रयासों के लगातार डेटा संरचना संस्करण का उपयोग करें। [[हास्केल (प्रोग्रामिंग भाषा)]] लाइब्रेरी अनऑर्डर्ड-कंटेनर लगातार मानचित्र को लागू करने और डेटा संरचनाओं को सेट करने के लिए इसका उपयोग करती है।<ref>Johan Tibell, A. [http://blog.johantibell.com/2012/03/announcing-unordered-containers-02.html Announcing unordered-containers 0.2]</ref> एक अन्य हास्केल लाइब्रेरी एसटीएम-कंटेनर [[सॉफ़्टवेयर ट्रांसेक्शनल मेमोरी]] के संदर्भ में उपयोग के लिए एल्गोरिदम को अनुकूलित करता है।<ref>Nikita Volkov, [https://nikita-volkov.github.io/stm-containers/ Announcing the "stm-containers" library], 2014</ref> एक [[जावास्क्रिप्ट]] एचएएमटी लाइब्रेरी <ref>{{cite web|url=https://github.com/mattbierner/hamt|title=mattbierner/hamt|website=GitHub|date=27 November 2022 }}</ref> क्लोजर कार्यान्वयन पर आधारित भी उपलब्ध है। [[ माणिक ]]<ref>{{cite web|url=https://github.com/rubinius/rubinius/blob/540a4b446991e4d5c956023d37ec4f95372d539d/kernel/common/hash_hamt.rb|title=रुबिनियस के HAMT की रूबी स्रोत फ़ाइल|website=[[GitHub]]|publisher=}}</ref> [[रूबी (प्रोग्रामिंग भाषा)]] के कार्यान्वयन में एक HAMT शामिल है, जो ज्यादातर रूबी में लिखा गया है लेकिन 3 के साथ<ref>https://github.com/rubinius/rubinius/blob/master/machine/builtin/system.cpp#L1724-L1802 {{Dead link|date=February 2022}}</ref> आदिम। एर्लैंग (प्रोग्रामिंग भाषा) में बड़े मानचित्र रिलीज़ 18.0 के बाद से आंतरिक रूप से एक पर्सिस्टेंट डेटा संरचना HAMT प्रतिनिधित्व का उपयोग करते हैं।<ref>{{Cite web | url=http://www.erlang.org/news/86 | title=Erlang Programming Language}}</ref> पोनी प्रोग्रामिंग भाषा अपने सतत संग्रह पैकेज में हैश मैप के लिए HAMT का उपयोग करती है।<ref>{{Cite web | url=https://github.com/ponylang/ponyc/blob/master/packages/collections/persistent/map.pony | title=horse: Pony is an open-source, actor-model, capabilities-secure, high performance programming language: Ponylang/ponyc| website=[[GitHub]]| date=2018-11-26}}</ref>
प्रोग्रामिंग भाषाएँ [[क्लोजर]],<ref>{{cite web|url=https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentHashMap.java|title=clojure/clojure|website=GitHub|date=8 December 2022 }}</ref> [[स्काला (प्रोग्रामिंग भाषा)]], और [[फ़्रीज (प्रोग्रामिंग भाषा)]] <ref>{{cite web|url=https://github.com/Frege/frege/blob/master/frege/data/HashMap.fr|title=Frege/frege|website=GitHub|date=7 December 2022 }}</ref> अपने मूल हैश मानचित्र प्रकार के लिए हैश सरणी मानचित्र किए गए प्रयासों के लगातार डेटा संरचना संस्करण का उपयोग करें। [[हास्केल (प्रोग्रामिंग भाषा)]] लाइब्रेरी अव्यवस्थित-धारक लगातार मानचित्र को लागू करने और डेटा संरचनाओं को सम्मुच्चय करने के लिए इसका उपयोग करती है। <ref>Johan Tibell, A. [http://blog.johantibell.com/2012/03/announcing-unordered-containers-02.html Announcing unordered-containers 0.2]</ref> एक अन्य हास्केल लाइब्रेरी एसटीएम-धारक [[सॉफ़्टवेयर ट्रांसेक्शनल मेमोरी]] के संदर्भ में उपयोग के लिए कलन विधि को अनुकूलित करता है। <ref>Nikita Volkov, [https://nikita-volkov.github.io/stm-containers/ Announcing the "stm-containers" library], 2014</ref> एक [[जावास्क्रिप्ट]] एचएएमटी लाइब्रेरी <ref>{{cite web|url=https://github.com/mattbierner/hamt|title=mattbierner/hamt|website=GitHub|date=27 November 2022 }}</ref> क्लोजर कार्यान्वयन पर आधारित भी उपलब्ध है। [[ माणिक |रुबिनियस]] <ref>{{cite web|url=https://github.com/rubinius/rubinius/blob/540a4b446991e4d5c956023d37ec4f95372d539d/kernel/common/hash_hamt.rb|title=रुबिनियस के HAMT की रूबी स्रोत फ़ाइल|website=[[GitHub]]|publisher=}}</ref> [[रूबी (प्रोग्रामिंग भाषा)]] के कार्यान्वयन में एक एचएएमटी सम्मिलित है, जो अधिकतर रूबी में लिखा गया है लेकिन 3 के साथ <ref>https://github.com/rubinius/rubinius/blob/master/machine/builtin/system.cpp#L1724-L1802 {{Dead link|date=February 2022}}</ref> एर्लैंग (प्रोग्रामिंग भाषा) में बड़े मानचित्र विमोचन 18.0 के बाद से आंतरिक रूप से एक पर्सिस्टेंट डेटा संरचना एचएएमटी प्रतिनिधित्व का उपयोग करते हैं। <ref>{{Cite web | url=http://www.erlang.org/news/86 | title=Erlang Programming Language}}</ref> पोनी प्रोग्रामिंग भाषा अपने सतत संग्रह पैकेज में हैश मानचित्र के लिए एचएएमटी का उपयोग करती है। <ref>{{Cite web | url=https://github.com/ponylang/ponyc/blob/master/packages/collections/persistent/map.pony | title=horse: Pony is an open-source, actor-model, capabilities-secure, high performance programming language: Ponylang/ponyc| website=[[GitHub]]| date=2018-11-26}}</ref>
आईएम और आईएम-आरसी क्रेट्स, जो रस्ट प्रोग्रामिंग भाषा के लिए लगातार संग्रह प्रकार प्रदान करते हैं, अपने लगातार हैश टेबल और हैश सेट के लिए एचएएमटी का उपयोग करते हैं।
 
<ref>{{cite web|url=https://docs.rs/im/|title=API docs for Rust im-rc crate}}</ref>
आईएम और आईएम-आरसी क्रेट्स, जो रस्ट प्रोग्रामिंग भाषा के लिए लगातार संग्रह प्रकार प्रदान करते हैं, अपने लगातार हैश सारिणी और हैश सम्मुच्चय के लिए एचएएमटी का उपयोग करते हैं।<ref>{{cite web|url=https://docs.rs/im/|title=API docs for Rust im-rc crate}}</ref> समवर्ती लॉक-मुक्त संस्करण <ref>Prokopec, A. [https://github.com/axel22/Ctries Implementation of Concurrent Hash Tries on GitHub]</ref> [[Ctrie|सीटीआरआई]] नामक हैश ट्री एक परिवर्तनीय थ्रेड-सुरक्षित कार्यान्वयन है जो प्रगति सुनिश्चित करता है। डेटा-संरचना सही सिद्ध हुई है <ref>Prokopec, A. et al. (2011) [http://infoscience.epfl.ch/record/166908/files/ctries-techreport.pdf Cache-Aware Lock-Free Concurrent Hash Tries]. Technical Report, 2011.</ref> - सीटीआरआई ऑपरेशंस में [[ परमाणुता (प्रोग्रामिंग) |अटॉमिसिटी (प्रोग्रामिंग)]], [[रैखिकता]] और लॉक-फ्रीडम गुण दिखाए गए हैं।
समवर्ती लॉक-मुक्त संस्करण<ref>Prokopec, A. [https://github.com/axel22/Ctries Implementation of Concurrent Hash Tries on GitHub]</ref> [[Ctrie]] नामक हैश ट्राइ एक परिवर्तनीय थ्रेड-सुरक्षित कार्यान्वयन है जो प्रगति सुनिश्चित करता है। डेटा-संरचना सही साबित हुई है<ref>Prokopec, A. et al. (2011) [http://infoscience.epfl.ch/record/166908/files/ctries-techreport.pdf Cache-Aware Lock-Free Concurrent Hash Tries]. Technical Report, 2011.</ref> - Ctrie ऑपरेशंस में [[ परमाणुता (प्रोग्रामिंग) ]], [[रैखिकता]] और [[ ताला मुक्त ]]|लॉक-फ्रीडम गुण दिखाए गए हैं।


== यह भी देखें ==
== यह भी देखें ==

Revision as of 19:30, 16 July 2023

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

संचालन

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

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

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

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

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

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

कार्यान्वयन

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

आईएम और आईएम-आरसी क्रेट्स, जो रस्ट प्रोग्रामिंग भाषा के लिए लगातार संग्रह प्रकार प्रदान करते हैं, अपने लगातार हैश सारिणी और हैश सम्मुच्चय के लिए एचएएमटी का उपयोग करते हैं।[11] समवर्ती लॉक-मुक्त संस्करण [12] सीटीआरआई नामक हैश ट्री एक परिवर्तनीय थ्रेड-सुरक्षित कार्यान्वयन है जो प्रगति सुनिश्चित करता है। डेटा-संरचना सही सिद्ध हुई है [13] - सीटीआरआई ऑपरेशंस में अटॉमिसिटी (प्रोग्रामिंग), रैखिकता और लॉक-फ्रीडम गुण दिखाए गए हैं।

यह भी देखें

संदर्भ

  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=227416’