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