मार्क-कॉम्पैक्ट एल्गोरिदम: Difference between revisions

From Vigyanwiki
(Created page with "{{Use dmy dates|date=August 2012}} कंप्यूटर विज्ञान में, मार्क-कॉम्पैक्ट कलन विधि एक...")
 
No edit summary
 
(7 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Use dmy dates|date=August 2012}}
[[कंप्यूटर विज्ञान]] में, '''मार्क-कॉम्पैक्ट एल्गोरिदम''' एक प्रकार का गार्बेज कलेक्शन एल्गोरिदम है जिसका उपयोग पहुंच योग्य मेमोरी को पुनः प्राप्त करने के लिए किया जाता है। मार्क-कॉम्पैक्ट एल्गोरिदम को मार्क-स्वीप एल्गोरिदम और चेनी की कॉपीिंग एल्गोरिदम का संयोजन माना जा सकता है। पहले, पहुंच योग्य ऑब्जेक्ट्स को चिह्नित किया जाता है, और फिर एक कॉम्पैक्टिंग चरण पहुंच योग्य (चिह्नित) ऑब्जेक्ट्स को हीप क्षेत्र को प्रारम्भ की ओर स्थानांतरित करता है। आधुनिक जेवीएम, [[माइक्रोसॉफ्ट]] के कॉमन लैंग्वेज रनटाइम और [[ग्लासगो हास्केल कंपाइलर]] द्वारा गार्बेज कलेक्शन को संकुचित किया जाता है।
[[कंप्यूटर विज्ञान]] में, मार्क-कॉम्पैक्ट [[कलन विधि]] एक प्रकार का [[कचरा संग्रहण (कंप्यूटर विज्ञान)]] एल्गोरिदम है जिसका उपयोग अप्राप्य मेमोरी को पुनः प्राप्त करने के लिए किया जाता है। मार्क-कॉम्पैक्ट एल्गोरिदम को मार्क-स्वीप एल्गोरिदम और चेनी के एल्गोरिदम | चेनी की कॉपीिंग एल्गोरिदम के संयोजन के रूप में माना जा सकता है। सबसे पहले, पहुंच योग्य वस्तुओं को चिह्नित किया जाता है, फिर एक कॉम्पैक्टिंग चरण पहुंच योग्य (चिह्नित) वस्तुओं को ढेर क्षेत्र की शुरुआत की ओर स्थानांतरित करता है। कॉम्पैक्टिंग कचरा संग्रहण का उपयोग आधुनिक [[जावा वर्चुअल मशीन]], [[माइक्रोसॉफ्ट]] की [[सामान्य भाषा रनटाइम]] और [[ग्लासगो हास्केल कंपाइलर]] द्वारा किया जाता है।


==एल्गोरिदम==
==एल्गोरिदम==
ढेर में जीवित वस्तुओं को मार्क-स्वीप एल्गोरिदम के समान तरीके से चिह्नित करने के बाद, ढेर अक्सर [[विखंडन (कंप्यूटर)]] होगा। मार्क-कॉम्पैक्ट एल्गोरिदम का लक्ष्य स्मृति में जीवित वस्तुओं को एक साथ स्थानांतरित करना है ताकि विखंडन समाप्त हो जाए। चुनौती स्थानांतरित वस्तुओं के सभी पॉइंटर्स को सही ढंग से अपडेट करने की है, जिनमें से अधिकांश में कॉम्पैक्शन के बाद नए मेमोरी पते होंगे। पॉइंटर अपडेट को संभालने के मुद्दे को अलग-अलग तरीकों से संभाला जाता है।
हीप में लाइव ऑब्जेक्ट्स को मार्क-स्वीप एल्गोरिदम के समान ही चिह्नित करने के बाद, हीप प्रायः खंडित हो जाएगा। मार्क-कॉम्पैक्ट एल्गोरिदम का लक्ष्य लाइव ऑब्जेक्ट्स को मेमोरी में एक साथ स्थानांतरित करना है ताकि विखंडन समाप्त हो जाए। चुनौती सभी पॉइंटर्स को स्थानांतरित ऑब्जेक्ट्स में सही ढंग से अपडेट करना है, जिनमें से अधिकांश में कॉम्पैक्शन के बाद नए मेमोरी पते होंगे। पॉइंटर अपडेट को संभालने के विषय को विभिन्न विधियों से नियंत्रित किया जाता है।


===तालिका-आधारित संघनन===
===टेबल-आधारित संघनन===
[[File:Table-based heap compaction flattened.svg|thumb|280px|टेबल-हीप संघनन एल्गोरिथ्म का चित्रण। जिन वस्तुओं को अंकन चरण ने पहुंच योग्य (लाइव) होने के लिए निर्धारित किया है वे रंगीन हैं, खाली स्थान खाली है।]]टेबल-आधारित एल्गोरिदम का वर्णन पहली बार 1967 में हेडन और वाइट द्वारा किया गया था।<ref>{{cite journal  
[[File:Table-based heap compaction flattened.svg|thumb|280px|टेबल-हीप संघनन एल्गोरिथ्म का चित्रण। जिन ऑब्जेक्ट्स को अंकन चरण ने पहुंच योग्य (लाइव) होने के लिए निर्धारित किया है वे रंगीन हैं, खाली स्थान खाली है।]]टेबल-आधारित एल्गोरिदम का वर्णन सबसे पहले 1967 में हेडन और वाइट द्वारा किया गया था।<ref>{{cite journal  
|author1=B. K. Haddon |author2=W. M. Waite
|author1=B. K. Haddon |author2=W. M. Waite
|title=A compaction procedure for variable-length storage elements
|title=A compaction procedure for variable-length storage elements
Line 16: Line 15:
|url=https://academic.oup.com/comjnl/article-pdf/10/2/162/963555/10-2-162.pdf|doi=10.1093/comjnl/10.2.162
|url=https://academic.oup.com/comjnl/article-pdf/10/2/162/963555/10-2-162.pdf|doi=10.1093/comjnl/10.2.162
|doi-access=free
|doi-access=free
}}</ref> यह ढेर में जीवित वस्तुओं के सापेक्ष स्थान को संरक्षित करता है, और केवल एक स्थिर मात्रा में ओवरहेड की आवश्यकता होती है।
}}</ref> यह हीप में लाइव ऑब्जेक्ट्स के सापेक्ष स्थान को सुरक्षित रखता है, और इसके लिए केवल एक स्थिर मात्रा में ओवरहेड की आवश्यकता होती है।


संघनन ढेर के नीचे (कम पते) से ऊपर (उच्च पते) की ओर बढ़ता है। जैसे ही जीवित (अर्थात, चिह्नित) वस्तुओं का सामना किया जाता है, उन्हें पहले उपलब्ध निम्न पते पर ले जाया जाता है, और स्थानांतरण जानकारी की ब्रेक तालिका में एक रिकॉर्ड जोड़ा जाता है। प्रत्येक लाइव ऑब्जेक्ट के लिए, ब्रेक टेबल में एक रिकॉर्ड में कॉम्पैक्शन से पहले ऑब्जेक्ट का मूल पता और कॉम्पैक्शन के बाद मूल पते और नए पते के बीच का अंतर शामिल होता है। ब्रेक टेबल को उस ढेर में संग्रहित किया जाता है जिसे संकुचित किया जा रहा है, लेकिन ऐसे क्षेत्र में जिसे अप्रयुक्त के रूप में चिह्नित किया गया है। यह सुनिश्चित करने के लिए कि संघनन हमेशा सफल होगा, ढेर में न्यूनतम ऑब्जेक्ट का आकार ब्रेक टेबल रिकॉर्ड से बड़ा या उसके समान होना चाहिए।
संघनन हीप के नीचे (लो एड्रेसस ) से शीर्ष (हाई एड्रेसस) तक होता है। जैसे ही लाइव (अर्थात् चिह्नित) ऑब्जेक्ट्स सामने आती हैं, उन्हें पहले उपलब्ध निम्न पते पर ले जाया जाता है, और स्थानांतरण जानकारी की ब्रेक तालिका में एक रिकॉर्ड जोड़ा जाता है। प्रत्येक लाइव ऑब्जेक्ट के लिए, '''ब्रेक टेबल''' में एक रिकॉर्ड में संपीड़न से पहले ऑब्जेक्ट का मूल पता और संपीड़न के बाद मूल पते और नए एड्रेस के बीच का अंतर सम्मिलित होता है। ब्रेक टेबल को उस हीप में संग्रहीत किया जाता है जिसे संकुचित किया जा रहा है, लेकिन उस क्षेत्र में जिसे अप्रयुक्त के रूप में चिह्नित किया गया है। यह सुनिश्चित करने के लिए कि संघनन हमेशा सफल रहेगा, हीप में न्यूनतम ऑब्जेक्ट का आकार ब्रेक टेबल रिकॉर्ड से बड़ा या उसके समान आकार का होना चाहिए।


जैसे-जैसे संघनन बढ़ता है, स्थानांतरित वस्तुएं ढेर के नीचे की ओर कॉपी हो जाती हैं। अंततः किसी ऑब्जेक्ट को ब्रेक टेबल द्वारा घेरी गई जगह पर कॉपी करने की आवश्यकता होगी, जिसे अब कहीं और स्थानांतरित किया जाना चाहिए। ब्रेक टेबल की ये गतिविधियां, (लेखकों द्वारा ''टेबल को रोल करना'' कहा जाता है) के कारण स्थानांतरण रिकॉर्ड अव्यवस्थित हो जाते हैं, जिसके लिए संघनन पूरा होने के बाद ब्रेक टेबल को [[तुलना क्रम]]बद्ध करने की आवश्यकता होती है। ब्रेक टेबल को सॉर्ट करने की लागत ''[[ बड़ा ओ अंकन ]]'' (''एन'' लॉग ''एन'') है, जहां ''एन'' जीवित वस्तुओं की संख्या है जो मार्क चरण में पाए गए थे कलन विधि।
जैसे-जैसे संघनन आगे बढ़ता है, स्थानांतरित वस्तुएँ हीप के नीचे की ओर प्रतिलिपि बनाई जाती हैं। अंततः, किसी ऑब्जेक्ट को ब्रेक टेबल द्वारा व्याप्त स्थान पर कॉपी करने की आवश्यकता होगी, जिसे अब कहीं और स्थानांतरित किया जाना चाहिए। ब्रेक टेबल के इन आंदोलनों, (लेखकों द्वारा ''टेबल को रोल करना'' कहा जाता है) के कारण स्थानांतरण रिकॉर्ड अव्यवस्थित हो जाते हैं, जिससे संघनन पूरा होने के बाद ब्रेक टेबल को क्रमबद्ध करने की आवश्यकता होती है। ब्रेक टेबल को सॉर्ट करने की लागत ''O''(''n'' log ''n'') है, जहां ''n'' उन लाइव ऑब्जेक्ट्स की संख्या है जो एल्गोरिदम के मार्क चरण में पाई गई थीं।


अंत में, ब्रेक टेबल रिलोकेशन रिकॉर्ड का उपयोग स्थानांतरित ऑब्जेक्ट के अंदर पॉइंटर फ़ील्ड को समायोजित करने के लिए किया जाता है। पॉइंटर्स के लिए लाइव ऑब्जेक्ट की जांच की जाती है, जिसे कुल रनिंग टाइम के लिए, यदि ब्रेक टेबल को सॉर्ट किया जाता है, तो ओ (लॉग ''एन'') समय में ''एन'' आकार की सॉर्ट की गई ब्रेक टेबल में देखा जा सकता है। 'ओ''(''एन'' लॉग ''एन'')। फिर पॉइंटर्स को स्थानांतरण तालिका में निर्दिष्ट राशि के अनुसार समायोजित किया जाता है।
अंत में, ब्रेक टेबल रिलोकेशन रिकॉर्ड का उपयोग स्थानांतरित ऑब्जेक्ट के अंदर पॉइंटर फ़ील्ड को समायोजित करने के लिए किया जाता है। पॉइंटर्स के लिए लाइव ऑब्जेक्ट की जांच की जाती है, जिसे O(log ''n'') समय में आकार ''n'' की सॉर्ट की गई ब्रेक टेबल में देखा जा सकता है यदि ब्रेक टेबल को ''O''(''n'' log ''n'') के कुल चलने वाले समय के लिए सॉर्ट किया जाता है। फिर पॉइंटर्स को स्थानांतरण तालिका में निर्दिष्ट राशि के अनुसार समायोजित किया जाता है।


===एलआईएसपी 2 एल्गोरिथम===
===एलआईएसपी (लिस्प) 2 एल्गोरिदम===
O(n log n) जटिलता से बचने के लिए, {{nowrap|[[LISP 2]]}} एल्गोरिदम ढेर के ऊपर से तीन अलग-अलग पासों का उपयोग करता है। इसके अलावा, ढेर वस्तुओं में एक अलग अग्रेषण सूचक स्लॉट होना चाहिए जिसका उपयोग कचरा संग्रहण के बाहर नहीं किया जाता है।
''O''(''n'' log ''n'') जटिलता से बचने के लिए, लिस्प 2 एल्गोरिथ्म ढेर पर तीन अलग-अलग चरणों का उपयोग करता है। इसके अलावा, हीप ऑब्जेक्ट में एक अलग फ़ॉरवर्डिंग पॉइंटर स्लॉट होना चाहिए जिसका उपयोग गार्बेज कलेक्शन के बाहर नहीं किया जाता है।


मानक अंकन के बाद, एल्गोरिथ्म निम्नलिखित तीन चरणों में आगे बढ़ता है:
मानक अंकन के बाद, एल्गोरिथ्म निम्नलिखित तीन चरणों में आगे बढ़ता है:


# जीवित वस्तुओं के लिए अग्रेषण स्थान की गणना करें।
# लाइव ऑब्जेक्ट के लिए अग्रेषण स्थान की गणना करें।
#* एक फ्री और लाइव पॉइंटर का ट्रैक रखें और ढेर की शुरुआत में दोनों को इनिशियलाइज़ करें।
#*''फ्री'' और ''लाइव'' पॉइंटर का ट्रैक रखें और हीप को प्रारम्भ में दोनों को आरंभ करें।
#* यदि लाइव पॉइंटर किसी लाइव ऑब्जेक्ट की ओर इशारा करता है, तो उस ऑब्जेक्ट के फॉरवर्डिंग पॉइंटर को वर्तमान फ्री पॉइंटर पर अपडेट करें और ऑब्जेक्ट के आकार के अनुसार फ्री पॉइंटर को बढ़ाएं।
#*यदि ''लाइव'' पॉइंटर किसी लाइव ऑब्जेक्ट को इंगित करता है, तो उस ऑब्जेक्ट के फ़ॉरवर्डिंग पॉइंटर को वर्तमान फ्री पॉइंटर पर अपडेट करें और ऑब्जेक्ट के आकार के अनुसार ''फ्री'' पॉइंटर को बढ़ाएं।
#* लाइव पॉइंटर को अगले ऑब्जेक्ट पर ले जाएं
#*''लाइव'' पॉइंटर को अगले ऑब्जेक्ट पर ले जाएं
#* जब लाइव पॉइंटर ढेर के अंत तक पहुंच जाए तो समाप्त करें।
#*जब ''लाइव'' पॉइंटर हीप के अंत तक पहुँच जाए तब समाप्त करें।
# सभी पॉइंटर्स को अपडेट करें
# सभी पॉइंटर्स को अपडेट करें
#* प्रत्येक लाइव ऑब्जेक्ट के लिए, उसके पॉइंटर्स को उन ऑब्जेक्ट्स के फॉरवर्डिंग पॉइंटर्स के अनुसार अपडेट करें जिन्हें वे इंगित करते हैं।
#* प्रत्येक ''लाइव'' ऑब्जेक्ट के लिए, उसके पॉइंटर्स को उन ऑब्जेक्ट्स के फॉरवर्डिंग पॉइंटर्स के अनुसार अपडेट करें जिन्हें वे इंगित करते हैं।
# वस्तुओं को स्थानांतरित करें
# ऑब्जेक्ट्स को स्थानांतरित करें
#* प्रत्येक लाइव ऑब्जेक्ट के लिए, उसके डेटा को उसके अग्रेषित स्थान पर ले जाएं।
#* प्रत्येक ''लाइव'' ऑब्जेक्ट के लिए, उसके डेटा को उसके अग्रेषित स्थान पर ले जाएं।


यह एल्गोरिदम ढेर के आकार पर O(n) है; इसमें तालिका-आधारित दृष्टिकोण की तुलना में बेहतर जटिलता है, लेकिन तालिका-आधारित दृष्टिकोण का n केवल उपयोग किए गए स्थान का आकार है, न कि संपूर्ण ढेर स्थान जैसा कि LISP2 एल्गोरिथ्म में है। हालाँकि, LISP2 एल्गोरिथ्म को लागू करना आसान है।
यह एल्गोरिदम हीप के आकार पर O(''n'') है; इसमें तालिका-आधारित दृष्टिकोण की तुलना में बेहतर जटिलता है, लेकिन तालिका-आधारित दृष्टिकोण का ''n'' केवल उपयोग किए गए स्थान का आकार है, न कि संपूर्ण हीप स्थान जैसा कि लिप्स2 एल्गोरिथ्म में है। हालाँकि, लिप्स2 एल्गोरिथ्म को प्रयुक्त करना आसान है।


==यह भी देखें==
==यह भी देखें==
Line 47: Line 46:
{{Reflist}}
{{Reflist}}


{{Memory management navbox}}
{{DEFAULTSORT:Mark-Compact Algorithm}}


{{DEFAULTSORT:Mark-Compact Algorithm}}[[Category: स्वचालित स्मृति प्रबंधन]] [[Category: मेमोरी प्रबंधन एल्गोरिदम]]  
[[Category:Created On 11/07/2023|Mark-Compact Algorithm]]
 
[[Category:Machine Translated Page|Mark-Compact Algorithm]]
 
[[Category:Pages with script errors|Mark-Compact Algorithm]]
 
[[Category:Templates Vigyan Ready]]
[[Category: Machine Translated Page]]
[[Category:मेमोरी प्रबंधन एल्गोरिदम|Mark-Compact Algorithm]]
[[Category:Created On 11/07/2023]]
[[Category:स्वचालित स्मृति प्रबंधन|Mark-Compact Algorithm]]

Latest revision as of 15:26, 31 July 2023

कंप्यूटर विज्ञान में, मार्क-कॉम्पैक्ट एल्गोरिदम एक प्रकार का गार्बेज कलेक्शन एल्गोरिदम है जिसका उपयोग पहुंच योग्य मेमोरी को पुनः प्राप्त करने के लिए किया जाता है। मार्क-कॉम्पैक्ट एल्गोरिदम को मार्क-स्वीप एल्गोरिदम और चेनी की कॉपीिंग एल्गोरिदम का संयोजन माना जा सकता है। पहले, पहुंच योग्य ऑब्जेक्ट्स को चिह्नित किया जाता है, और फिर एक कॉम्पैक्टिंग चरण पहुंच योग्य (चिह्नित) ऑब्जेक्ट्स को हीप क्षेत्र को प्रारम्भ की ओर स्थानांतरित करता है। आधुनिक जेवीएम, माइक्रोसॉफ्ट के कॉमन लैंग्वेज रनटाइम और ग्लासगो हास्केल कंपाइलर द्वारा गार्बेज कलेक्शन को संकुचित किया जाता है।

एल्गोरिदम

हीप में लाइव ऑब्जेक्ट्स को मार्क-स्वीप एल्गोरिदम के समान ही चिह्नित करने के बाद, हीप प्रायः खंडित हो जाएगा। मार्क-कॉम्पैक्ट एल्गोरिदम का लक्ष्य लाइव ऑब्जेक्ट्स को मेमोरी में एक साथ स्थानांतरित करना है ताकि विखंडन समाप्त हो जाए। चुनौती सभी पॉइंटर्स को स्थानांतरित ऑब्जेक्ट्स में सही ढंग से अपडेट करना है, जिनमें से अधिकांश में कॉम्पैक्शन के बाद नए मेमोरी पते होंगे। पॉइंटर अपडेट को संभालने के विषय को विभिन्न विधियों से नियंत्रित किया जाता है।

टेबल-आधारित संघनन

टेबल-हीप संघनन एल्गोरिथ्म का चित्रण। जिन ऑब्जेक्ट्स को अंकन चरण ने पहुंच योग्य (लाइव) होने के लिए निर्धारित किया है वे रंगीन हैं, खाली स्थान खाली है।

टेबल-आधारित एल्गोरिदम का वर्णन सबसे पहले 1967 में हेडन और वाइट द्वारा किया गया था।[1] यह हीप में लाइव ऑब्जेक्ट्स के सापेक्ष स्थान को सुरक्षित रखता है, और इसके लिए केवल एक स्थिर मात्रा में ओवरहेड की आवश्यकता होती है।

संघनन हीप के नीचे (लो एड्रेसस ) से शीर्ष (हाई एड्रेसस) तक होता है। जैसे ही लाइव (अर्थात् चिह्नित) ऑब्जेक्ट्स सामने आती हैं, उन्हें पहले उपलब्ध निम्न पते पर ले जाया जाता है, और स्थानांतरण जानकारी की ब्रेक तालिका में एक रिकॉर्ड जोड़ा जाता है। प्रत्येक लाइव ऑब्जेक्ट के लिए, ब्रेक टेबल में एक रिकॉर्ड में संपीड़न से पहले ऑब्जेक्ट का मूल पता और संपीड़न के बाद मूल पते और नए एड्रेस के बीच का अंतर सम्मिलित होता है। ब्रेक टेबल को उस हीप में संग्रहीत किया जाता है जिसे संकुचित किया जा रहा है, लेकिन उस क्षेत्र में जिसे अप्रयुक्त के रूप में चिह्नित किया गया है। यह सुनिश्चित करने के लिए कि संघनन हमेशा सफल रहेगा, हीप में न्यूनतम ऑब्जेक्ट का आकार ब्रेक टेबल रिकॉर्ड से बड़ा या उसके समान आकार का होना चाहिए।

जैसे-जैसे संघनन आगे बढ़ता है, स्थानांतरित वस्तुएँ हीप के नीचे की ओर प्रतिलिपि बनाई जाती हैं। अंततः, किसी ऑब्जेक्ट को ब्रेक टेबल द्वारा व्याप्त स्थान पर कॉपी करने की आवश्यकता होगी, जिसे अब कहीं और स्थानांतरित किया जाना चाहिए। ब्रेक टेबल के इन आंदोलनों, (लेखकों द्वारा टेबल को रोल करना कहा जाता है) के कारण स्थानांतरण रिकॉर्ड अव्यवस्थित हो जाते हैं, जिससे संघनन पूरा होने के बाद ब्रेक टेबल को क्रमबद्ध करने की आवश्यकता होती है। ब्रेक टेबल को सॉर्ट करने की लागत O(n log n) है, जहां n उन लाइव ऑब्जेक्ट्स की संख्या है जो एल्गोरिदम के मार्क चरण में पाई गई थीं।

अंत में, ब्रेक टेबल रिलोकेशन रिकॉर्ड का उपयोग स्थानांतरित ऑब्जेक्ट के अंदर पॉइंटर फ़ील्ड को समायोजित करने के लिए किया जाता है। पॉइंटर्स के लिए लाइव ऑब्जेक्ट की जांच की जाती है, जिसे O(log n) समय में आकार n की सॉर्ट की गई ब्रेक टेबल में देखा जा सकता है यदि ब्रेक टेबल को O(n log n) के कुल चलने वाले समय के लिए सॉर्ट किया जाता है। फिर पॉइंटर्स को स्थानांतरण तालिका में निर्दिष्ट राशि के अनुसार समायोजित किया जाता है।

एलआईएसपी (लिस्प) 2 एल्गोरिदम

O(n log n) जटिलता से बचने के लिए, लिस्प 2 एल्गोरिथ्म ढेर पर तीन अलग-अलग चरणों का उपयोग करता है। इसके अलावा, हीप ऑब्जेक्ट में एक अलग फ़ॉरवर्डिंग पॉइंटर स्लॉट होना चाहिए जिसका उपयोग गार्बेज कलेक्शन के बाहर नहीं किया जाता है।

मानक अंकन के बाद, एल्गोरिथ्म निम्नलिखित तीन चरणों में आगे बढ़ता है:

  1. लाइव ऑब्जेक्ट के लिए अग्रेषण स्थान की गणना करें।
    • फ्री और लाइव पॉइंटर का ट्रैक रखें और हीप को प्रारम्भ में दोनों को आरंभ करें।
    • यदि लाइव पॉइंटर किसी लाइव ऑब्जेक्ट को इंगित करता है, तो उस ऑब्जेक्ट के फ़ॉरवर्डिंग पॉइंटर को वर्तमान फ्री पॉइंटर पर अपडेट करें और ऑब्जेक्ट के आकार के अनुसार फ्री पॉइंटर को बढ़ाएं।
    • लाइव पॉइंटर को अगले ऑब्जेक्ट पर ले जाएं
    • जब लाइव पॉइंटर हीप के अंत तक पहुँच जाए तब समाप्त करें।
  2. सभी पॉइंटर्स को अपडेट करें
    • प्रत्येक लाइव ऑब्जेक्ट के लिए, उसके पॉइंटर्स को उन ऑब्जेक्ट्स के फॉरवर्डिंग पॉइंटर्स के अनुसार अपडेट करें जिन्हें वे इंगित करते हैं।
  3. ऑब्जेक्ट्स को स्थानांतरित करें
    • प्रत्येक लाइव ऑब्जेक्ट के लिए, उसके डेटा को उसके अग्रेषित स्थान पर ले जाएं।

यह एल्गोरिदम हीप के आकार पर O(n) है; इसमें तालिका-आधारित दृष्टिकोण की तुलना में बेहतर जटिलता है, लेकिन तालिका-आधारित दृष्टिकोण का n केवल उपयोग किए गए स्थान का आकार है, न कि संपूर्ण हीप स्थान जैसा कि लिप्स2 एल्गोरिथ्म में है। हालाँकि, लिप्स2 एल्गोरिथ्म को प्रयुक्त करना आसान है।

यह भी देखें

संदर्भ

  1. ↑ B. K. Haddon; W. M. Waite (August 1967). "A compaction procedure for variable-length storage elements" (PDF). Computer Journal. 10 (2): 162–165. doi:10.1093/comjnl/10.2.162.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=मार्क-कॉम्पैक्ट_एल्गोरिदम&oldid=231284’