बी-हीप
बी-हीप एक बाइनरी हीप है जिसे एक सिंगल पेज में उपतर कोण रखने के लिए लागू किया जाता है। जब वर्चुअल मेमोरी का उपयोग करके बड़े हीप के लिए पारंपरिक लागू के संदर्भ में, इससे यह पृष्ठों तक पहुंचे हुए पृष्ठों की संख्या को दस गुना तक कम करता है। प्रायः प्रत्येक स्तर को एक अलग पेज में रखने के लिए एक एरे में तत्वों का मैपिंग पारंपरिक रूप से किया जाता है।[1]
वर्चुअल मेमोरी या कैश का उपयोग करने वाले कंप्यूटर में कुछ अन्य हीप वेरिएंट्स भी हैं जो कारगर होते हैं, जैसे कैश-अवेयर एल्गोरिदम, के-हीप्स[2] और वैन एमडे बोएस लेआउट्स।[3]
प्रेरणा
पारंपरिक रूप से, बाइनरी ट्रीज को निरंतर मेमोरी में एक n -> {2n, 2n+1} नियम के अनुसार व्यवस्थित किया जाता है, जिसका अर्थ है कि अगर किसी नोड का स्थान n पर है, तो उसके बाएं और दाएं बच्चे को सरणी में स्थान 2n और 2n+1 पर लिया जाता है। रूट पोज़िशन 1 पर होता है। बाइनरी ट्रीज पर एक सामान्य कार्रवाई उसके लंबवत ट्रावर्सल होती है; यानी एक खोजी गई नोड पर पहुंचने के लिए ट्री के स्तरों के माध्यम से नीचे कदम रखना। हालांकि, आधुनिक कंप्यूटरों में मेमोरी को वर्चुअल मेमोरी में पेजों में व्यवस्थित करने के तरीके के कारण, बाइनरी ट्री को इस तरीके से व्यवस्थित करना अत्यंत अप्रभावी हो सकता है। कारण यह है कि, जब ट्री में गहराई से भ्रमण करते हैं, तो अगले नोड तक की दूरी गणितशास्त्रीय रूप से वृद्धि होती है, इसलिए प्रत्येक अगले नोड को प्राप्त करने पर संभावित रूप से वह अलग मेमोरी पेज पर होगा। यह पेज मिसेज की संख्या बढ़ाएगा, जो बहुत महंगा होता है। बी-हीप इस समस्या का समाधान करता है जिसे बच्चा नोड को मेमोरी में एक अलग तरीके से व्यवस्थित करके किया जाता है, जिससे वह संभवतः संपूर्ण पेज के भीतर उपतर कोण को स्थान देने का प्रयास करता है। इसलिए, जब एक लंबवत ट्रावर्सल प्रारंभ होता है, कई निरंतर प्राप्त नोड एक ही पेज में होते हैं, जिससे पेज मिसेज की संख्या कम होती है।
कार्यान्वयन
विस्तार से कहें तो, एक बी-हीप को निम्नलिखित तरीके से लागू किया जा सकता है। पौल-हेनिंग कैंप[4] ने नोडों के लेआउट के लिए दो विकल्प दिए हैं: एक विकल्प में पेज प्रति दो स्थान बर्बाद होते हैं, लेकिन ट्री की सख्त बाइनरी संरचना को संरक्षित रखा जाता है, और एक दूसरा विकल्प जिसमें पेजों के सभी उपलब्ध स्थान का उपयोग किया जाता है, लेकिन ट्री एक पेज में एक स्तर तक ही विस्तारित होती है (उस स्तर पर नोडों के पास केवल एक बच्चा होता है)। किसी भी स्थिति में, एक महत्वपूर्ण बिंदु यह है कि एक पेज छोड़ने पर, दोनों बच्चे नोड हमेशा एक सामान्य दूसरे पेज में होते हैं, क्योंकि लंबवत ट्रावर्सल में एल्गोरिदम सामान्य रूप से माता-पिता के साथ दोनों बच्चों की तुलना करता है जारी रखने के लिए। इस कारण से, प्रत्येक पेज में कहा जा सकता है कि वह दो समानांतर उपतर कोण को संबोधित करती है, जो एक दूसरे के साथ आपस में घुसे हुए होते हैं। पेज खुद को m-वारी ट्री के रूप में देखा जा सकता है, और क्योंकि प्रत्येक पेज में केरों का आधा अंश होगा (पेज के भीतर), "पेज का ट्री" pagesize/2 का विभाजन कारक रखता है।
मूल कार्य
बिना-हीप के विभिन्न लेआउट के खिलाफ, एक क्लासिक एरे-जैसे व्यवस्था के मुकाबले, बिना-हीप में पैरेंट (parent) फ़ंक्शन अधिक जटिल होता है क्योंकि नोड के पैरेंट का इंडेक्स पेज में जहां है, उस पर निर्भर करता है। पेज के भीतर स्थानों को 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.
