मार्क-कॉम्पैक्ट एल्गोरिदम: Difference between revisions
No edit summary |
|||
| (5 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
[[कंप्यूटर विज्ञान]] में, '''मार्क-कॉम्पैक्ट | [[कंप्यूटर विज्ञान]] में, '''मार्क-कॉम्पैक्ट एल्गोरिदम''' एक प्रकार का गार्बेज कलेक्शन एल्गोरिदम है जिसका उपयोग पहुंच योग्य मेमोरी को पुनः प्राप्त करने के लिए किया जाता है। मार्क-कॉम्पैक्ट एल्गोरिदम को मार्क-स्वीप एल्गोरिदम और चेनी की कॉपीिंग एल्गोरिदम का संयोजन माना जा सकता है। पहले, पहुंच योग्य ऑब्जेक्ट्स को चिह्नित किया जाता है, और फिर एक कॉम्पैक्टिंग चरण पहुंच योग्य (चिह्नित) ऑब्जेक्ट्स को हीप क्षेत्र को प्रारम्भ की ओर स्थानांतरित करता है। आधुनिक जेवीएम, [[माइक्रोसॉफ्ट]] के कॉमन लैंग्वेज रनटाइम और [[ग्लासगो हास्केल कंपाइलर]] द्वारा गार्बेज कलेक्शन को संकुचित किया जाता है। | ||
==एल्गोरिदम== | ==एल्गोरिदम== | ||
हीप में लाइव ऑब्जेक्ट्स को मार्क-स्वीप एल्गोरिदम के समान ही चिह्नित करने के बाद, हीप | हीप में लाइव ऑब्जेक्ट्स को मार्क-स्वीप एल्गोरिदम के समान ही चिह्नित करने के बाद, हीप प्रायः खंडित हो जाएगा। मार्क-कॉम्पैक्ट एल्गोरिदम का लक्ष्य लाइव ऑब्जेक्ट्स को मेमोरी में एक साथ स्थानांतरित करना है ताकि विखंडन समाप्त हो जाए। चुनौती सभी पॉइंटर्स को स्थानांतरित ऑब्जेक्ट्स में सही ढंग से अपडेट करना है, जिनमें से अधिकांश में कॉम्पैक्शन के बाद नए मेमोरी पते होंगे। पॉइंटर अपडेट को संभालने के विषय को विभिन्न विधियों से नियंत्रित किया जाता है। | ||
=== | ===टेबल-आधारित संघनन=== | ||
[[File:Table-based heap compaction flattened.svg|thumb|280px|टेबल-हीप संघनन एल्गोरिथ्म का चित्रण। जिन | [[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 17: | Line 17: | ||
}}</ref> यह हीप में लाइव ऑब्जेक्ट्स के सापेक्ष स्थान को सुरक्षित रखता है, और इसके लिए केवल एक स्थिर मात्रा में ओवरहेड की आवश्यकता होती है। | }}</ref> यह हीप में लाइव ऑब्जेक्ट्स के सापेक्ष स्थान को सुरक्षित रखता है, और इसके लिए केवल एक स्थिर मात्रा में ओवरहेड की आवश्यकता होती है। | ||
संघनन हीप के नीचे (लो एड्रेसस ) से शीर्ष (हाई एड्रेसस) तक होता है। जैसे ही लाइव (अर्थात् चिह्नित) ऑब्जेक्ट्स सामने आती हैं, उन्हें पहले उपलब्ध निम्न पते पर ले जाया जाता है, और स्थानांतरण जानकारी की ब्रेक तालिका में एक रिकॉर्ड जोड़ा जाता है। प्रत्येक लाइव ऑब्जेक्ट के लिए, '''ब्रेक टेबल''' में एक रिकॉर्ड में संपीड़न से पहले ऑब्जेक्ट का मूल पता और संपीड़न के बाद मूल पते और नए एड्रेस के बीच का अंतर | संघनन हीप के नीचे (लो एड्रेसस ) से शीर्ष (हाई एड्रेसस) तक होता है। जैसे ही लाइव (अर्थात् चिह्नित) ऑब्जेक्ट्स सामने आती हैं, उन्हें पहले उपलब्ध निम्न पते पर ले जाया जाता है, और स्थानांतरण जानकारी की ब्रेक तालिका में एक रिकॉर्ड जोड़ा जाता है। प्रत्येक लाइव ऑब्जेक्ट के लिए, '''ब्रेक टेबल''' में एक रिकॉर्ड में संपीड़न से पहले ऑब्जेक्ट का मूल पता और संपीड़न के बाद मूल पते और नए एड्रेस के बीच का अंतर सम्मिलित होता है। ब्रेक टेबल को उस हीप में संग्रहीत किया जाता है जिसे संकुचित किया जा रहा है, लेकिन उस क्षेत्र में जिसे अप्रयुक्त के रूप में चिह्नित किया गया है। यह सुनिश्चित करने के लिए कि संघनन हमेशा सफल रहेगा, हीप में न्यूनतम ऑब्जेक्ट का आकार ब्रेक टेबल रिकॉर्ड से बड़ा या उसके समान आकार का होना चाहिए। | ||
जैसे-जैसे संघनन आगे बढ़ता है, स्थानांतरित वस्तुएँ हीप के नीचे की ओर प्रतिलिपि बनाई जाती हैं। अंततः, किसी ऑब्जेक्ट को ब्रेक टेबल द्वारा व्याप्त स्थान पर कॉपी करने की आवश्यकता होगी, जिसे अब कहीं और स्थानांतरित किया जाना चाहिए। ब्रेक टेबल के इन आंदोलनों, (लेखकों द्वारा ''टेबल को रोल करना'' कहा जाता है) के कारण स्थानांतरण रिकॉर्ड अव्यवस्थित हो जाते हैं, जिससे संघनन पूरा होने के बाद ब्रेक टेबल को क्रमबद्ध करने की आवश्यकता होती है। ब्रेक टेबल को सॉर्ट करने की लागत ''O''(''n'' log ''n'') है, जहां ''n'' उन | जैसे-जैसे संघनन आगे बढ़ता है, स्थानांतरित वस्तुएँ हीप के नीचे की ओर प्रतिलिपि बनाई जाती हैं। अंततः, किसी ऑब्जेक्ट को ब्रेक टेबल द्वारा व्याप्त स्थान पर कॉपी करने की आवश्यकता होगी, जिसे अब कहीं और स्थानांतरित किया जाना चाहिए। ब्रेक टेबल के इन आंदोलनों, (लेखकों द्वारा ''टेबल को रोल करना'' कहा जाता है) के कारण स्थानांतरण रिकॉर्ड अव्यवस्थित हो जाते हैं, जिससे संघनन पूरा होने के बाद ब्रेक टेबल को क्रमबद्ध करने की आवश्यकता होती है। ब्रेक टेबल को सॉर्ट करने की लागत ''O''(''n'' log ''n'') है, जहां ''n'' उन लाइव ऑब्जेक्ट्स की संख्या है जो एल्गोरिदम के मार्क चरण में पाई गई थीं। | ||
अंत में, ब्रेक टेबल रिलोकेशन रिकॉर्ड का उपयोग स्थानांतरित ऑब्जेक्ट के अंदर पॉइंटर फ़ील्ड को समायोजित करने के लिए किया जाता है। पॉइंटर्स के लिए लाइव ऑब्जेक्ट की जांच की जाती है, जिसे O(log ''n'') समय में आकार ''n'' की सॉर्ट की गई ब्रेक टेबल में देखा जा सकता है यदि ब्रेक टेबल को ''O''(''n'' log ''n'') के कुल चलने वाले समय के लिए सॉर्ट किया जाता है। फिर पॉइंटर्स को स्थानांतरण तालिका में निर्दिष्ट राशि के अनुसार समायोजित किया जाता है। | अंत में, ब्रेक टेबल रिलोकेशन रिकॉर्ड का उपयोग स्थानांतरित ऑब्जेक्ट के अंदर पॉइंटर फ़ील्ड को समायोजित करने के लिए किया जाता है। पॉइंटर्स के लिए लाइव ऑब्जेक्ट की जांच की जाती है, जिसे O(log ''n'') समय में आकार ''n'' की सॉर्ट की गई ब्रेक टेबल में देखा जा सकता है यदि ब्रेक टेबल को ''O''(''n'' log ''n'') के कुल चलने वाले समय के लिए सॉर्ट किया जाता है। फिर पॉइंटर्स को स्थानांतरण तालिका में निर्दिष्ट राशि के अनुसार समायोजित किया जाता है। | ||
===एलआईएसपी 2 | ===एलआईएसपी (लिस्प) 2 एल्गोरिदम=== | ||
O( | ''O''(''n'' log ''n'') जटिलता से बचने के लिए, लिस्प 2 एल्गोरिथ्म ढेर पर तीन अलग-अलग चरणों का उपयोग करता है। इसके अलावा, हीप ऑब्जेक्ट में एक अलग फ़ॉरवर्डिंग पॉइंटर स्लॉट होना चाहिए जिसका उपयोग गार्बेज कलेक्शन के बाहर नहीं किया जाता है। | ||
मानक अंकन के बाद, एल्गोरिथ्म निम्नलिखित तीन चरणों में आगे बढ़ता है: | मानक अंकन के बाद, एल्गोरिथ्म निम्नलिखित तीन चरणों में आगे बढ़ता है: | ||
# | # लाइव ऑब्जेक्ट के लिए अग्रेषण स्थान की गणना करें। | ||
#* | #*''फ्री'' और ''लाइव'' पॉइंटर का ट्रैक रखें और हीप को प्रारम्भ में दोनों को आरंभ करें। | ||
#* यदि लाइव पॉइंटर किसी लाइव ऑब्जेक्ट | #*यदि ''लाइव'' पॉइंटर किसी लाइव ऑब्जेक्ट को इंगित करता है, तो उस ऑब्जेक्ट के फ़ॉरवर्डिंग पॉइंटर को वर्तमान फ्री पॉइंटर पर अपडेट करें और ऑब्जेक्ट के आकार के अनुसार ''फ्री'' पॉइंटर को बढ़ाएं। | ||
#* लाइव पॉइंटर को अगले ऑब्जेक्ट पर ले जाएं | #*''लाइव'' पॉइंटर को अगले ऑब्जेक्ट पर ले जाएं | ||
#* जब लाइव पॉइंटर हीप के अंत तक | #*जब ''लाइव'' पॉइंटर हीप के अंत तक पहुँच जाए तब समाप्त करें। | ||
# सभी पॉइंटर्स को अपडेट करें | # सभी पॉइंटर्स को अपडेट करें | ||
#* प्रत्येक लाइव ऑब्जेक्ट के लिए, उसके पॉइंटर्स को उन ऑब्जेक्ट्स के फॉरवर्डिंग पॉइंटर्स के अनुसार अपडेट करें जिन्हें वे इंगित करते हैं। | #* प्रत्येक ''लाइव'' ऑब्जेक्ट के लिए, उसके पॉइंटर्स को उन ऑब्जेक्ट्स के फॉरवर्डिंग पॉइंटर्स के अनुसार अपडेट करें जिन्हें वे इंगित करते हैं। | ||
# | # ऑब्जेक्ट्स को स्थानांतरित करें | ||
#* प्रत्येक लाइव ऑब्जेक्ट के लिए, उसके डेटा को उसके अग्रेषित स्थान पर ले जाएं। | #* प्रत्येक ''लाइव'' ऑब्जेक्ट के लिए, उसके डेटा को उसके अग्रेषित स्थान पर ले जाएं। | ||
यह एल्गोरिदम हीप के आकार पर O(n) है; इसमें तालिका-आधारित दृष्टिकोण की तुलना में बेहतर जटिलता है, लेकिन तालिका-आधारित दृष्टिकोण का n केवल उपयोग किए गए स्थान का आकार है, न कि संपूर्ण हीप स्थान जैसा कि | यह एल्गोरिदम हीप के आकार पर O(''n'') है; इसमें तालिका-आधारित दृष्टिकोण की तुलना में बेहतर जटिलता है, लेकिन तालिका-आधारित दृष्टिकोण का ''n'' केवल उपयोग किए गए स्थान का आकार है, न कि संपूर्ण हीप स्थान जैसा कि लिप्स2 एल्गोरिथ्म में है। हालाँकि, लिप्स2 एल्गोरिथ्म को प्रयुक्त करना आसान है। | ||
==यह भी देखें== | ==यह भी देखें== | ||
| Line 46: | Line 46: | ||
{{Reflist}} | {{Reflist}} | ||
{{ | {{DEFAULTSORT:Mark-Compact Algorithm}} | ||
[[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: | [[Category:मेमोरी प्रबंधन एल्गोरिदम|Mark-Compact Algorithm]] | ||
[[Category: | [[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 एल्गोरिथ्म ढेर पर तीन अलग-अलग चरणों का उपयोग करता है। इसके अलावा, हीप ऑब्जेक्ट में एक अलग फ़ॉरवर्डिंग पॉइंटर स्लॉट होना चाहिए जिसका उपयोग गार्बेज कलेक्शन के बाहर नहीं किया जाता है।
मानक अंकन के बाद, एल्गोरिथ्म निम्नलिखित तीन चरणों में आगे बढ़ता है:
- लाइव ऑब्जेक्ट के लिए अग्रेषण स्थान की गणना करें।
- फ्री और लाइव पॉइंटर का ट्रैक रखें और हीप को प्रारम्भ में दोनों को आरंभ करें।
- यदि लाइव पॉइंटर किसी लाइव ऑब्जेक्ट को इंगित करता है, तो उस ऑब्जेक्ट के फ़ॉरवर्डिंग पॉइंटर को वर्तमान फ्री पॉइंटर पर अपडेट करें और ऑब्जेक्ट के आकार के अनुसार फ्री पॉइंटर को बढ़ाएं।
- लाइव पॉइंटर को अगले ऑब्जेक्ट पर ले जाएं
- जब लाइव पॉइंटर हीप के अंत तक पहुँच जाए तब समाप्त करें।
- सभी पॉइंटर्स को अपडेट करें
- प्रत्येक लाइव ऑब्जेक्ट के लिए, उसके पॉइंटर्स को उन ऑब्जेक्ट्स के फॉरवर्डिंग पॉइंटर्स के अनुसार अपडेट करें जिन्हें वे इंगित करते हैं।
- ऑब्जेक्ट्स को स्थानांतरित करें
- प्रत्येक लाइव ऑब्जेक्ट के लिए, उसके डेटा को उसके अग्रेषित स्थान पर ले जाएं।
यह एल्गोरिदम हीप के आकार पर O(n) है; इसमें तालिका-आधारित दृष्टिकोण की तुलना में बेहतर जटिलता है, लेकिन तालिका-आधारित दृष्टिकोण का n केवल उपयोग किए गए स्थान का आकार है, न कि संपूर्ण हीप स्थान जैसा कि लिप्स2 एल्गोरिथ्म में है। हालाँकि, लिप्स2 एल्गोरिथ्म को प्रयुक्त करना आसान है।
यह भी देखें
संदर्भ
- ↑ 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.
