बी-हीप: Difference between revisions
(minor changes) |
(Work done) |
||
| Line 1: | Line 1: | ||
बी-हीप | '''बी-हीप''' जिसे [[ बाइनरी ढेर |बाइनरी हीप]] कहा जाता है जिसे किसी सिंगल पृष्ठ में सबट्रीज़ रखने के लिए लागू किया जाता है। जब [[ आभासी मेमोरी |वर्चुअल मेमोरी]] का उपयोग करके बड़े हीप के लिए पारंपरिक कार्यान्वयन के संदर्भ में, इससे यह एक्सेस किए गए पृष्ठों की संख्या को दस गुना तक कम कर देता है। किसी ऐरे में स्थानों के लिए तत्वों की पारंपरिक मैपिंग लगभग हर स्तर को एक अलग पृष्ठ में रखती है।<ref name=":0">{{cite journal | ||
|first=Poul-Henning |last=Kamp | |first=Poul-Henning |last=Kamp | ||
|url=https://queue.acm.org/detail.cfm?id=1814327 | |url=https://queue.acm.org/detail.cfm?id=1814327 | ||
| Line 7: | Line 7: | ||
}}</ref> | }}</ref> | ||
वर्चुअल मेमोरी या कैश का उपयोग करने वाले कंप्यूटर में कुछ अन्य हीप वेरिएंट्स | वर्चुअल मेमोरी या कैश का उपयोग करने वाले कंप्यूटर में कुछ अन्य हीप वेरिएंट्स जैसे [[कैश-विस्मृत एल्गोरिथ्म|कैश-ऑब्लिवियस एल्गोरिदम]], के-हीप्स<ref>{{cite journal |last1=Naor |first1=Dalit |last2=Martel |first2=Charles U. |last3=Matloff |first3=Norman S. |title=वर्चुअल मेमोरी वातावरण में प्राथमिकता कतार संरचनाओं का प्रदर्शन|doi=10.1093/comjnl/34.5.428 |journal=[[The Computer Journal |Comput. J.]] |volume=34 |issue=5 |pages=428–437 |year=1991 |doi-access=free}}</ref> और वैन एमडे बोएस लेआउट्स, भी होते है जो कार्यकारी होते है।<ref>{{cite journal |author-link1=Peter van Emde Boas |last1=van Emde Boas |first1=P. |last2=Kaas |first2=R. |last3=Zijlstra |first3=E. |year=1976 |title=एक कुशल प्राथमिकता कतार का डिज़ाइन और कार्यान्वयन|journal=[[Mathematical Systems Theory]] |volume=10 |pages=99–127 |doi=10.1007/BF01683268|s2cid=8105468 }}</ref> | ||
== | == प्रयोजन == | ||
पारंपरिक रूप से, [[ द्विआधारी वृक्ष |बाइनरी ट्रीज]] को | पारंपरिक रूप से, [[ द्विआधारी वृक्ष |बाइनरी ट्रीज]] को कोनज़ीक्युटिव मेमोरी में एक <code>n -> {2n, 2n+1}</code> नियम के अनुसार व्यवस्थित किया जाता है, जिसका अर्थ है कि यदि किसी नोड का स्थान <code>n</code> पर है, तो उसके बाएं और दाएं चाइल्ड को ऐरे में स्थान <code>2n</code> और <code>2n+1</code> पर लिया जाता है। रूट पोज़िशन 1 पर होता है। बाइनरी ट्री पर एक सामान्य संक्रिया उसके लंबवत ट्रावर्सल होती है; अर्थात एक खोजी गई नोड पर पहुंचने के लिए ट्री के स्तरों के माध्यम से नीचे कदम रखना। हालांकि, आधुनिक कंप्यूटरों में मेमोरी को वर्चुअल मेमोरी में पृष्ठों में व्यवस्थित करने के तरीके के कारण, बाइनरी ट्री को इस तरीके से व्यवस्थित करना अत्यंत अप्रभावी हो सकता है। कारण यह है कि, जब ट्री में डीप ट्रैवर्स करता हैं, तो अगले नोड तक की दूरी घातांकी रूप से वृद्धि होती है, इसलिए प्रत्येक अगले नोड को प्राप्त करने पर संभावित रूप से वह अलग मेमोरी पृष्ठ पर होगा। यह पृष्ठ मिसेज की संख्या बढ़ाएगा, जो बहुत महंगा होता है। बी-हीप इस समस्या का समाधान करता है जिसे चाइल्ड नोड को मेमोरी में एक अलग तरीके से व्यवस्थित करके किया जाता है, जिससे वह संभवतः संपूर्ण पृष्ठ के भीतर सबट्री को स्थान देने का प्रयास करता है। इसलिए, जब एक लंबवत ट्रावर्सल प्रारंभ होता है, कई निरंतर प्राप्त नोड एक ही पृष्ठ में होते हैं, जिससे पृष्ठ मिसेज की संख्या कम होती है। | ||
==कार्यान्वयन== | ==कार्यान्वयन== | ||
विस्तारित रूप से, बी-हीप को निम्नलिखित विधि से लागू किया जा सकता है। पौल-हेनिंग कैंप<ref>{{Cite web|url=http://phk.freebsd.dk/B-Heap/queue.html |title=आपके द्वारा गलत किया जा रहा है|first=Poul-Henning |last=Kamp |website=phk.freebsd.dk |access-date=2019-06-08}}</ref> ने नोडों के लेआउट के लिए दो विकल्प दिए हैं: विकल्प में पृष्ठ प्रति दो स्थान निरर्थक होते हैं, लेकिन ट्री की स्ट्रिक्ट बाइनरी स्ट्रक्चर को संरक्षित रखा जाता है, और एक दूसरा विकल्प जिसमें पृष्ठों के सभी उपलब्ध स्थान का उपयोग किया जाता है, लेकिन ट्री एक पृष्ठ में एक स्तर तक ही विस्तारित होती है (उस स्तर पर नोडों के पास केवल एक चाइल्ड होता है)। किसी भी स्थिति में, एक महत्वपूर्ण बिंदु यह है कि एक पृष्ठ छोड़ने पर, दोनों चाइल्ड नोड हमेशा एक सामान्य दूसरे पृष्ठ में होते हैं, क्योंकि लंबवत ट्रावर्सल में एल्गोरिदम सामान्य रूप से माता-पिता के साथ दोनों बच्चों की तुलना करता है जारी रखने के लिए। इस कारण से, प्रत्येक पृष्ठ में कहा जा सकता है कि वह दो समानांतर सबट्री को संबोधित करती है, जो एक दूसरे के साथ आपस में घुसे हुए होते हैं। पृष्ठों को स्वयं एक एम-एरी ट्री के रूप में देखा जा सकता है, और चूंकि प्रत्येक पृष्ठ में अर्ध तत्व लीव्स (पृष्ठ के भीतर) होंगे, इसलिए "पृष्ठों के ट्री" में <code>pagesize/2</code> का विभाजन कारक होता है। | |||
=== | ===पैरेंट फंक्शन=== | ||
क्लासिक एरे-जैसे अभिविन्यास के विपरीत, बी-हीप में पैरेंट फ़ंक्शन अधिक कॉम्प्लेक्स होता है क्योंकि नोड के पैरेंट का इंडेक्स पृष्ठ के कहां पर है, उस पर निर्भर करके अलग-अलग तरीके से गणना की जानी चाहिए। मान लें कि पृष्ठ के भीतर स्थानों को 0 से <code>pagesize</code> तक नामंकित किया गया है, तो पैरेंट फ़ंक्शन निम्नलिखित रूप में हो सकता है। | |||
नोड्स 0 और 1 के लिए, इनका उपयोग केवल उस वैरिएंट में किया जाता है जो सभी संभावित स्थान का शोषण कर रहा है। इस स्थिति में, दोनों नोड्स का मूल सूचकांक समान है, यह एक अलग पृष्ठ में है, और उस पृष्ठ के भीतर इसकी विशिष्ट ऑफसेट केवल वर्तमान पृष्ठ संख्या पर निर्भर करती है। विशेष रूप से, मूल पृष्ठ संख्या की गणना करने के लिए, बस वर्तमान नोड के पृष्ठ संख्या को " | नोड्स 0 और 1 के लिए, इनका उपयोग केवल उस वैरिएंट में किया जाता है जो सभी संभावित स्थान का शोषण कर रहा है। इस स्थिति में, दोनों नोड्स का मूल सूचकांक समान है, यह एक अलग पृष्ठ में है, और उस पृष्ठ के भीतर इसकी विशिष्ट ऑफसेट केवल वर्तमान पृष्ठ संख्या पर निर्भर करती है। विशेष रूप से, मूल पृष्ठ संख्या की गणना करने के लिए, बस वर्तमान नोड के पृष्ठ संख्या को "पृष्ठ ट्री" विभाजन कारक से विभाजित करें, जो कि <code>pagesize/2</code> है। पृष्ठ के भीतर सही ऑफसेट प्राप्त करने के लिए, विचार करें कि यह मूल पृष्ठ के भीतर लीफ नोड्स में से एक होना चाहिए, इसलिए ऑफसेट <code>pagesize/2</code> से प्रारंभ करें। तब पृष्ठ की वर्तमान संख्या और पैरेंट-पृष्ठ की संख्या के बीच का अंतर जोड़ें, पैरेंट-पृष्ठ के बाद का पहला पृष्ठ इंडेक्स (<code>pagesize/2</code>) है, उसे घटा दें। | ||
नोड 2 और 3 के लिए, पैरेंट मोड के आधार पर भिन्न होते हैं। स्थान बचाने वाले मोड में, पैरेंट सिर्फ नोड 0 और 1 होते हैं, इसलिए केवल 2 से घटाना होता है। दूसरी ओर, | नोड 2 और 3 के लिए, पैरेंट मोड के आधार पर भिन्न होते हैं। स्थान बचाने वाले मोड में, पैरेंट सिर्फ नोड 0 और 1 होते हैं, इसलिए केवल 2 से घटाना होता है। दूसरी ओर, स्ट्रिक्ट-बाइनरी-ट्री-मोड में, ये नोड नोड 0 और 1 के बजाय पृष्ठ की रूट्स होते हैं, और इसलिए उनका समान पैरेंट उसी तरीके से गणना किया जाता है जैसा कि पहले विवरणित किया गया है। | ||
बाकी सभी नोडों के लिए, उनके पैरेंट समान | बाकी सभी नोडों के लिए, उनके पैरेंट समान पृष्ठ के भीतर होगा, और उनके पृष्ठ के भीतरी स्थान को 2 से विभाजित करना पर्याप्त है, पृष्ठ संख्या को बदलते हुए नहीं। | ||
==यह भी देखें== | ==यह भी देखें== | ||
Revision as of 07:43, 24 July 2023
बी-हीप जिसे बाइनरी हीप कहा जाता है जिसे किसी सिंगल पृष्ठ में सबट्रीज़ रखने के लिए लागू किया जाता है। जब वर्चुअल मेमोरी का उपयोग करके बड़े हीप के लिए पारंपरिक कार्यान्वयन के संदर्भ में, इससे यह एक्सेस किए गए पृष्ठों की संख्या को दस गुना तक कम कर देता है। किसी ऐरे में स्थानों के लिए तत्वों की पारंपरिक मैपिंग लगभग हर स्तर को एक अलग पृष्ठ में रखती है।[1]
वर्चुअल मेमोरी या कैश का उपयोग करने वाले कंप्यूटर में कुछ अन्य हीप वेरिएंट्स जैसे कैश-ऑब्लिवियस एल्गोरिदम, के-हीप्स[2] और वैन एमडे बोएस लेआउट्स, भी होते है जो कार्यकारी होते है।[3]
प्रयोजन
पारंपरिक रूप से, बाइनरी ट्रीज को कोनज़ीक्युटिव मेमोरी में एक n -> {2n, 2n+1} नियम के अनुसार व्यवस्थित किया जाता है, जिसका अर्थ है कि यदि किसी नोड का स्थान n पर है, तो उसके बाएं और दाएं चाइल्ड को ऐरे में स्थान 2n और 2n+1 पर लिया जाता है। रूट पोज़िशन 1 पर होता है। बाइनरी ट्री पर एक सामान्य संक्रिया उसके लंबवत ट्रावर्सल होती है; अर्थात एक खोजी गई नोड पर पहुंचने के लिए ट्री के स्तरों के माध्यम से नीचे कदम रखना। हालांकि, आधुनिक कंप्यूटरों में मेमोरी को वर्चुअल मेमोरी में पृष्ठों में व्यवस्थित करने के तरीके के कारण, बाइनरी ट्री को इस तरीके से व्यवस्थित करना अत्यंत अप्रभावी हो सकता है। कारण यह है कि, जब ट्री में डीप ट्रैवर्स करता हैं, तो अगले नोड तक की दूरी घातांकी रूप से वृद्धि होती है, इसलिए प्रत्येक अगले नोड को प्राप्त करने पर संभावित रूप से वह अलग मेमोरी पृष्ठ पर होगा। यह पृष्ठ मिसेज की संख्या बढ़ाएगा, जो बहुत महंगा होता है। बी-हीप इस समस्या का समाधान करता है जिसे चाइल्ड नोड को मेमोरी में एक अलग तरीके से व्यवस्थित करके किया जाता है, जिससे वह संभवतः संपूर्ण पृष्ठ के भीतर सबट्री को स्थान देने का प्रयास करता है। इसलिए, जब एक लंबवत ट्रावर्सल प्रारंभ होता है, कई निरंतर प्राप्त नोड एक ही पृष्ठ में होते हैं, जिससे पृष्ठ मिसेज की संख्या कम होती है।
कार्यान्वयन
विस्तारित रूप से, बी-हीप को निम्नलिखित विधि से लागू किया जा सकता है। पौल-हेनिंग कैंप[4] ने नोडों के लेआउट के लिए दो विकल्प दिए हैं: विकल्प में पृष्ठ प्रति दो स्थान निरर्थक होते हैं, लेकिन ट्री की स्ट्रिक्ट बाइनरी स्ट्रक्चर को संरक्षित रखा जाता है, और एक दूसरा विकल्प जिसमें पृष्ठों के सभी उपलब्ध स्थान का उपयोग किया जाता है, लेकिन ट्री एक पृष्ठ में एक स्तर तक ही विस्तारित होती है (उस स्तर पर नोडों के पास केवल एक चाइल्ड होता है)। किसी भी स्थिति में, एक महत्वपूर्ण बिंदु यह है कि एक पृष्ठ छोड़ने पर, दोनों चाइल्ड नोड हमेशा एक सामान्य दूसरे पृष्ठ में होते हैं, क्योंकि लंबवत ट्रावर्सल में एल्गोरिदम सामान्य रूप से माता-पिता के साथ दोनों बच्चों की तुलना करता है जारी रखने के लिए। इस कारण से, प्रत्येक पृष्ठ में कहा जा सकता है कि वह दो समानांतर सबट्री को संबोधित करती है, जो एक दूसरे के साथ आपस में घुसे हुए होते हैं। पृष्ठों को स्वयं एक एम-एरी ट्री के रूप में देखा जा सकता है, और चूंकि प्रत्येक पृष्ठ में अर्ध तत्व लीव्स (पृष्ठ के भीतर) होंगे, इसलिए "पृष्ठों के ट्री" में pagesize/2 का विभाजन कारक होता है।
पैरेंट फंक्शन
क्लासिक एरे-जैसे अभिविन्यास के विपरीत, बी-हीप में पैरेंट फ़ंक्शन अधिक कॉम्प्लेक्स होता है क्योंकि नोड के पैरेंट का इंडेक्स पृष्ठ के कहां पर है, उस पर निर्भर करके अलग-अलग तरीके से गणना की जानी चाहिए। मान लें कि पृष्ठ के भीतर स्थानों को 0 से pagesize तक नामंकित किया गया है, तो पैरेंट फ़ंक्शन निम्नलिखित रूप में हो सकता है।
नोड्स 0 और 1 के लिए, इनका उपयोग केवल उस वैरिएंट में किया जाता है जो सभी संभावित स्थान का शोषण कर रहा है। इस स्थिति में, दोनों नोड्स का मूल सूचकांक समान है, यह एक अलग पृष्ठ में है, और उस पृष्ठ के भीतर इसकी विशिष्ट ऑफसेट केवल वर्तमान पृष्ठ संख्या पर निर्भर करती है। विशेष रूप से, मूल पृष्ठ संख्या की गणना करने के लिए, बस वर्तमान नोड के पृष्ठ संख्या को "पृष्ठ ट्री" विभाजन कारक से विभाजित करें, जो कि pagesize/2 है। पृष्ठ के भीतर सही ऑफसेट प्राप्त करने के लिए, विचार करें कि यह मूल पृष्ठ के भीतर लीफ नोड्स में से एक होना चाहिए, इसलिए ऑफसेट pagesize/2 से प्रारंभ करें। तब पृष्ठ की वर्तमान संख्या और पैरेंट-पृष्ठ की संख्या के बीच का अंतर जोड़ें, पैरेंट-पृष्ठ के बाद का पहला पृष्ठ इंडेक्स (pagesize/2) है, उसे घटा दें।
नोड 2 और 3 के लिए, पैरेंट मोड के आधार पर भिन्न होते हैं। स्थान बचाने वाले मोड में, पैरेंट सिर्फ नोड 0 और 1 होते हैं, इसलिए केवल 2 से घटाना होता है। दूसरी ओर, स्ट्रिक्ट-बाइनरी-ट्री-मोड में, ये नोड नोड 0 और 1 के बजाय पृष्ठ की रूट्स होते हैं, और इसलिए उनका समान पैरेंट उसी तरीके से गणना किया जाता है जैसा कि पहले विवरणित किया गया है।
बाकी सभी नोडों के लिए, उनके पैरेंट समान पृष्ठ के भीतर होगा, और उनके पृष्ठ के भीतरी स्थान को 2 से विभाजित करना पर्याप्त है, पृष्ठ संख्या को बदलते हुए नहीं।
यह भी देखें
संदर्भ
- ↑ Kamp, Poul-Henning (2020-07-26). "You're Doing It Wrong". ACM Queue.
- ↑ Naor, Dalit; Martel, Charles U.; Matloff, Norman S. (1991). "वर्चुअल मेमोरी वातावरण में प्राथमिकता कतार संरचनाओं का प्रदर्शन". Comput. J. 34 (5): 428–437. doi:10.1093/comjnl/34.5.428.
- ↑ van Emde Boas, P.; Kaas, R.; Zijlstra, E. (1976). "एक कुशल प्राथमिकता कतार का डिज़ाइन और कार्यान्वयन". Mathematical Systems Theory. 10: 99–127. doi:10.1007/BF01683268. S2CID 8105468.
- ↑ Kamp, Poul-Henning. "आपके द्वारा गलत किया जा रहा है". phk.freebsd.dk. Retrieved 2019-06-08.
बाहरी संबंध
- Implementations at https://github.com/varnish/Varnish-Cache/blob/master/lib/libvarnish/binary_heap.c and http://phk.freebsd.dk/B-Heap/binheap.c
- Generic heap implementation with B-heap support.
- For more on van Emde Boas layouts see Benjamin Sach Descent into Cache-Oblivion or Cache-oblivious data structures.
