बी-हीप - Revision history

Manidh at 06:20, 28 July 2023

2023-07-28T06:20:49Z

← Older revision		Revision as of 11:50, 28 July 2023
Line 35:		Line 35:
	*For more on van Emde Boas layouts see Benjamin Sach [https://web.archive.org/web/20110927000044/http://www.cs.bris.ac.uk/Research/Seminars/departmental/2008-03-13_DeptSeminar_BenSach.pdf Descent into Cache-Oblivion] or [http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx Cache-oblivious data structures].		*For more on van Emde Boas layouts see Benjamin Sach [https://web.archive.org/web/20110927000044/http://www.cs.bris.ac.uk/Research/Seminars/departmental/2008-03-13_DeptSeminar_BenSach.pdf Descent into Cache-Oblivion] or [http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx Cache-oblivious data structures].

	{{DEFAULTSORT:B-Heap}}~~[[Category: ढेर (डेटा संरचनाएं)]]~~		{{DEFAULTSORT:B-Heap}}

			[[Category:Created On 10/07/2023\|B-Heap]]
			[[Category:Machine Translated Page\|B-Heap]]
	[[Category: Machine Translated Page]]		[[Category:Pages with script errors\|B-Heap]]
	[[Category:~~Created On 10/07/2023~~]]		[[Category:Templates Vigyan Ready]]
	[[Category:Vigyan Ready]]		[[Category:ढेर (डेटा संरचनाएं)\|B-Heap]]

Indicwiki: 6 revisions imported from :alpha:बी-हीप

2023-07-28T05:06:39Z

6 revisions imported from alpha:बी-हीप

← Older revision	Revision as of 10:36, 28 July 2023
(No difference)

alpha>Neeraja: added Category:Vigyan Ready using HotCat

2023-07-27T06:46:06Z

added Category:Vigyan Ready using HotCat

← Older revision		Revision as of 12:16, 27 July 2023
Line 41:		Line 41:
	[[Category: Machine Translated Page]]		[[Category: Machine Translated Page]]
	[[Category:Created On 10/07/2023]]		[[Category:Created On 10/07/2023]]
			[[Category:Vigyan Ready]]

alpha>Sugatha at 08:24, 25 July 2023

2023-07-25T08:24:54Z

← Older revision		Revision as of 13:54, 25 July 2023
Line 1:		Line 1:
	'''बी-हीप''' जिसे [[ बाइनरी ढेर \|बाइनरी हीप]] कहा जाता है जिसे किसी सिंगल पृष्ठ में सबट्रीज़ रखने के लिए लागू किया जाता है। जब [[ आभासी मेमोरी \|वर्चुअल मेमोरी]] का उपयोग करके ~~बड़े~~ हीप के लिए पारंपरिक कार्यान्वयन के संदर्भ में, इससे यह एक्सेस किए गए पृष्ठों की संख्या को दस गुना तक कम कर देता है। किसी ऐरे में स्थानों के लिए तत्वों की पारंपरिक मैपिंग लगभग हर स्तर को एक अलग पृष्ठ में रखती है।<ref name=":0">{{cite journal		'''बी-हीप''' जिसे [[ बाइनरी ढेर \|बाइनरी हीप]] कहा जाता है जिसे किसी सिंगल पृष्ठ में सबट्रीज़ रखने के लिए लागू किया जाता है। जब [[ आभासी मेमोरी \|वर्चुअल मेमोरी]] का उपयोग करके बिंग हीप के लिए पारंपरिक कार्यान्वयन के संदर्भ में, इससे यह एक्सेस किए गए पृष्ठों की संख्या को दस गुना तक कम कर देता है। किसी ऐरे में स्थानों के लिए तत्वों की पारंपरिक मैपिंग लगभग हर स्तर को एक अलग पृष्ठ में रखती है।<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

alpha>Abhishekk: Work done

2023-07-24T02:13:14Z

Work done

Show changes

alpha>Abhishekk: minor changes

2023-07-23T17:15:19Z

minor changes

Show changes

alpha>Deepak: Deepak moved page बी-ढेर to बी-हीप without leaving a redirect

2023-07-21T05:56:02Z

Deepak moved page बी-ढेर to बी-हीप without leaving a redirect

← Older revision	Revision as of 11:26, 21 July 2023
(No difference)

alpha>Indicwiki: Created page with "बी-हीप एक बाइनरी ढेर है जिसे सबट्रीज़ को एक पेज (कंप्यूटर मेमोरी)..."

2023-07-10T06:23:08Z

Created page with "बी-हीप एक बाइनरी ढेर है जिसे सबट्रीज़ को एक पेज (कंप्यूटर मेमोरी)..."

New page

बी-हीप एक [[ बाइनरी ढेर ]] है जिसे सबट्रीज़ को एक पेज (कंप्यूटर मेमोरी) में रखने के लिए लागू किया जाता है। यह पारंपरिक कार्यान्वयन की तुलना में [[ आभासी मेमोरी ]] का उपयोग करते समय बड़े ढेर के लिए एक्सेस किए गए पृष्ठों की संख्या को दस गुना तक कम कर देता है।<ref name=":0">{{cite journal
|first=Poul-Henning |last=Kamp
|url=https://queue.acm.org/detail.cfm?id=1814327
|title=You're Doing It Wrong
|journal=[[ACM Queue]]
|date=2020-07-26
}}</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 पर है। बाइनरी पेड़ों पर एक सामान्य ऑपरेशन ऊर्ध्वाधर ट्रैवर्सल है; किसी खोजे गए नोड पर पहुंचने के लिए पेड़ के स्तर से नीचे उतरना। हालाँकि, जिस तरह से आधुनिक कंप्यूटरों पर मेमोरी को वर्चुअल मेमोरी में पृष्ठों में व्यवस्थित किया जाता है, उसके कारण बाइनरी ट्री को बिछाने की यह योजना अत्यधिक अप्रभावी हो सकती है। इसका कारण यह है कि, पेड़ में गहराई से जाने पर, अगले नोड की दूरी तेजी से बढ़ती है, इसलिए पुनर्प्राप्त किया गया प्रत्येक अगला नोड संभवतः एक अलग मेमोरी पेज पर होगा। इससे Cache (कंप्यूटिंग) की संख्या बढ़ जाएगी, जो बहुत महंगी हैं।
बी-हीप मेमोरी में चाइल्ड नोड्स को एक अलग तरीके से बिछाकर इस समस्या को हल करता है, एक ही पेज के भीतर उप-वृक्षों को रखने की यथासंभव कोशिश करता है। इसलिए, जैसे-जैसे वर्टिकल ट्रैवर्सल आगे बढ़ता है, लगातार पुनर्प्राप्त किए गए कई नोड एक ही पेज में आ जाएंगे, जिससे पेज मिस होने की संख्या कम हो जाएगी।

==कार्यान्वयन==
विस्तार से, बी-हीप को निम्नलिखित तरीके से लागू किया जा सकता है। पॉल-हेनिंग काम्प<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 के लिए, इनका उपयोग केवल उस संस्करण में किया जाता है जो सभी संभावित स्थान का शोषण कर रहा है। इस मामले में, दोनों नोड्स का मूल सूचकांक समान है, यह एक अलग पृष्ठ में है, और उस पृष्ठ के भीतर इसकी विशिष्ट ऑफसेट केवल वर्तमान पृष्ठ संख्या पर निर्भर करती है। विशेष रूप से, मूल पृष्ठ संख्या की गणना करने के लिए, बस वर्तमान नोड के पृष्ठ संख्या को पृष्ठ वृक्ष के विभाजन कारक से विभाजित करें, जो है <code>pagesize/2</code>. पृष्ठ के भीतर सही ऑफसेट प्राप्त करने के लिए, विचार करें कि यह मूल पृष्ठ के भीतर लीफ नोड्स में से एक होना चाहिए, इसलिए ऑफसेट से शुरू करें <code>pagesize/2</code>. फिर वर्तमान पृष्ठ संख्या और मूल पृष्ठ संख्या के बीच का अंतर जोड़ें, मूल पृष्ठ के सूचकांक में मूल नोड होने के बाद पहले पृष्ठ से एक घटाएं (<code>pagesize/2</code>).

नोड 2 और 3 के लिए, मोड के आधार पर पैरेंट भिन्न होता है। स्पेस-सेविंग मोड में, पैरेंट्स क्रमशः 0 और 1 नोड होते हैं, इसलिए किसी को केवल 2 से घटाना होता है। दूसरी ओर, स्ट्रिक्ट-बाइनरी-ट्री-मोड में, ये नोड पेज की जड़ें होते हैं 0 और 1 का, और इसलिए उनके सामान्य माता-पिता की गणना ऊपर वर्णित तरीके से की जाती है।

अन्य सभी नोड्स के लिए, उनके माता-पिता एक ही पृष्ठ के भीतर होंगे, और यह पृष्ठ संख्या को बदले बिना, उनके पृष्ठ के भीतर उनके ऑफसेट को 2 से विभाजित करने के लिए पर्याप्त है।

==यह भी देखें==
* [[डी-एरी ढेर]]

==संदर्भ==
{{Reflist}}

==बाहरी संबंध==
*Implementations at https://github.com/varnish/Varnish-Cache/blob/master/lib/libvarnish/binary_heap.c and http://phk.freebsd.dk/B-Heap/binheap.c
*[https://github.com/valyala/gheap Generic heap implementation with B-heap support].
*For more on van Emde Boas layouts see Benjamin Sach [https://web.archive.org/web/20110927000044/http://www.cs.bris.ac.uk/Research/Seminars/departmental/2008-03-13_DeptSeminar_BenSach.pdf Descent into Cache-Oblivion] or [http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx Cache-oblivious data structures].

{{DEFAULTSORT:B-Heap}}[[Category: ढेर (डेटा संरचनाएं)]]

[[Category: Machine Translated Page]]
[[Category:Created On 10/07/2023]]