मार्क-कॉम्पैक्ट एल्गोरिदम: Difference between revisions
No edit summary |
|||
| Line 1: | Line 1: | ||
[[कंप्यूटर विज्ञान]] में, '''मार्क-कॉम्पैक्ट एल्गोरिथम''' एक प्रकार का गार्बेज कलेक्शन एल्गोरिदम है जिसका उपयोग पहुंच योग्य मेमोरी को पुनः प्राप्त करने के लिए किया जाता है। मार्क-कॉम्पैक्ट एल्गोरिदम को मार्क-स्वीप एल्गोरिदम और चेनी की कॉपीिंग एल्गोरिदम का संयोजन माना जा सकता है। पहले, पहुंच योग्य वस्तुओं को चिह्नित किया जाता है, और फिर एक कॉम्पैक्टिंग चरण पहुंच योग्य (चिह्नित) वस्तुओं को | [[कंप्यूटर विज्ञान]] में, '''मार्क-कॉम्पैक्ट एल्गोरिथम''' एक प्रकार का गार्बेज कलेक्शन एल्गोरिदम है जिसका उपयोग पहुंच योग्य मेमोरी को पुनः प्राप्त करने के लिए किया जाता है। मार्क-कॉम्पैक्ट एल्गोरिदम को मार्क-स्वीप एल्गोरिदम और चेनी की कॉपीिंग एल्गोरिदम का संयोजन माना जा सकता है। पहले, पहुंच योग्य वस्तुओं को चिह्नित किया जाता है, और फिर एक कॉम्पैक्टिंग चरण पहुंच योग्य (चिह्नित) वस्तुओं को हीप क्षेत्र की शुरुआत की ओर स्थानांतरित करता है। आधुनिक जेवीएम, [[माइक्रोसॉफ्ट]] के कॉमन लैंग्वेज रनटाइम और [[ग्लासगो हास्केल कंपाइलर]] द्वारा गार्बेज कलेक्शन को संकुचित किया जाता है। | ||
==एल्गोरिदम== | ==एल्गोरिदम== | ||
| Line 5: | Line 5: | ||
===तालिका-आधारित संघनन=== | ===तालिका-आधारित संघनन=== | ||
[[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 15: | 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) जटिलता से बचने के लिए, {{nowrap|[[LISP 2]]}} एल्गोरिदम हीप के ऊपर से तीन अलग-अलग पासों का उपयोग करता है। इसके अलावा, हीप वस्तुओं में एक अलग अग्रेषण सूचक स्लॉट होना चाहिए जिसका उपयोग कचरा संग्रहण के बाहर नहीं किया जाता है। | ||
मानक अंकन के बाद, एल्गोरिथ्म निम्नलिखित तीन चरणों में आगे बढ़ता है: | मानक अंकन के बाद, एल्गोरिथ्म निम्नलिखित तीन चरणों में आगे बढ़ता है: | ||
# जीवित वस्तुओं के लिए अग्रेषण स्थान की गणना करें। | # जीवित वस्तुओं के लिए अग्रेषण स्थान की गणना करें। | ||
#* एक फ्री और लाइव पॉइंटर का ट्रैक रखें और | #* एक फ्री और लाइव पॉइंटर का ट्रैक रखें और हीप की शुरुआत में दोनों को इनिशियलाइज़ करें। | ||
#* यदि लाइव पॉइंटर किसी लाइव ऑब्जेक्ट की ओर इशारा करता है, तो उस ऑब्जेक्ट के फॉरवर्डिंग पॉइंटर को वर्तमान फ्री पॉइंटर पर अपडेट करें और ऑब्जेक्ट के आकार के अनुसार फ्री पॉइंटर को बढ़ाएं। | #* यदि लाइव पॉइंटर किसी लाइव ऑब्जेक्ट की ओर इशारा करता है, तो उस ऑब्जेक्ट के फॉरवर्डिंग पॉइंटर को वर्तमान फ्री पॉइंटर पर अपडेट करें और ऑब्जेक्ट के आकार के अनुसार फ्री पॉइंटर को बढ़ाएं। | ||
#* लाइव पॉइंटर को अगले ऑब्जेक्ट पर ले जाएं | #* लाइव पॉइंटर को अगले ऑब्जेक्ट पर ले जाएं | ||
#* जब लाइव पॉइंटर | #* जब लाइव पॉइंटर हीप के अंत तक पहुंच जाए तो समाप्त करें। | ||
# सभी पॉइंटर्स को अपडेट करें | # सभी पॉइंटर्स को अपडेट करें | ||
#* प्रत्येक लाइव ऑब्जेक्ट के लिए, उसके पॉइंटर्स को उन ऑब्जेक्ट्स के फॉरवर्डिंग पॉइंटर्स के अनुसार अपडेट करें जिन्हें वे इंगित करते हैं। | #* प्रत्येक लाइव ऑब्जेक्ट के लिए, उसके पॉइंटर्स को उन ऑब्जेक्ट्स के फॉरवर्डिंग पॉइंटर्स के अनुसार अपडेट करें जिन्हें वे इंगित करते हैं। | ||
| Line 38: | Line 38: | ||
#* प्रत्येक लाइव ऑब्जेक्ट के लिए, उसके डेटा को उसके अग्रेषित स्थान पर ले जाएं। | #* प्रत्येक लाइव ऑब्जेक्ट के लिए, उसके डेटा को उसके अग्रेषित स्थान पर ले जाएं। | ||
यह एल्गोरिदम | यह एल्गोरिदम हीप के आकार पर O(n) है; इसमें तालिका-आधारित दृष्टिकोण की तुलना में बेहतर जटिलता है, लेकिन तालिका-आधारित दृष्टिकोण का n केवल उपयोग किए गए स्थान का आकार है, न कि संपूर्ण हीप स्थान जैसा कि LISP2 एल्गोरिथ्म में है। हालाँकि, LISP2 एल्गोरिथ्म को लागू करना आसान है। | ||
==यह भी देखें== | ==यह भी देखें== | ||
Revision as of 06:27, 19 July 2023
कंप्यूटर विज्ञान में, मार्क-कॉम्पैक्ट एल्गोरिथम एक प्रकार का गार्बेज कलेक्शन एल्गोरिदम है जिसका उपयोग पहुंच योग्य मेमोरी को पुनः प्राप्त करने के लिए किया जाता है। मार्क-कॉम्पैक्ट एल्गोरिदम को मार्क-स्वीप एल्गोरिदम और चेनी की कॉपीिंग एल्गोरिदम का संयोजन माना जा सकता है। पहले, पहुंच योग्य वस्तुओं को चिह्नित किया जाता है, और फिर एक कॉम्पैक्टिंग चरण पहुंच योग्य (चिह्नित) वस्तुओं को हीप क्षेत्र की शुरुआत की ओर स्थानांतरित करता है। आधुनिक जेवीएम, माइक्रोसॉफ्ट के कॉमन लैंग्वेज रनटाइम और ग्लासगो हास्केल कंपाइलर द्वारा गार्बेज कलेक्शन को संकुचित किया जाता है।
एल्गोरिदम
हीप में लाइव ऑब्जेक्ट्स को मार्क-स्वीप एल्गोरिदम के समान ही चिह्नित करने के बाद, हीप अक्सर खंडित हो जाएगा। मार्क-कॉम्पैक्ट एल्गोरिदम का लक्ष्य जीवित वस्तुओं को मेमोरी में एक साथ स्थानांतरित करना है ताकि विखंडन समाप्त हो जाए। चुनौती सभी पॉइंटर्स को स्थानांतरित ऑब्जेक्ट्स में सही ढंग से अपडेट करना है, जिनमें से अधिकांश में कॉम्पैक्शन के बाद नए मेमोरी पते होंगे। पॉइंटर अपडेट को संभालने के विषय को विभिन्न विधियों से नियंत्रित किया जाता है।
तालिका-आधारित संघनन
टेबल-आधारित एल्गोरिदम का वर्णन सबसे पहले 1967 में हेडन और वाइट द्वारा किया गया था।[1] यह हीप में लाइव ऑब्जेक्ट्स के सापेक्ष स्थान को सुरक्षित रखता है, और इसके लिए केवल एक स्थिर मात्रा में ओवरहेड की आवश्यकता होती है।
संघनन हीप के नीचे (लो एड्रेसस ) से शीर्ष (हाई एड्रेसस) तक होता है। जैसे ही लाइव (अर्थात् चिह्नित) ऑब्जेक्ट्स सामने आती हैं, उन्हें पहले उपलब्ध निम्न पते पर ले जाया जाता है, और स्थानांतरण जानकारी की ब्रेक तालिका में एक रिकॉर्ड जोड़ा जाता है। प्रत्येक लाइव ऑब्जेक्ट के लिए, ब्रेक टेबल में एक रिकॉर्ड में संपीड़न से पहले ऑब्जेक्ट का मूल पता और संपीड़न के बाद मूल पते और नए एड्रेस के बीच का अंतर शामिल होता है। ब्रेक टेबल को उस हीप में संग्रहीत किया जाता है जिसे संकुचित किया जा रहा है, लेकिन उस क्षेत्र में जिसे अप्रयुक्त के रूप में चिह्नित किया गया है। यह सुनिश्चित करने के लिए कि संघनन हमेशा सफल रहेगा, हीप में न्यूनतम ऑब्जेक्ट का आकार ब्रेक टेबल रिकॉर्ड से बड़ा या उसके समान आकार का होना चाहिए।
जैसे-जैसे संघनन आगे बढ़ता है, स्थानांतरित वस्तुएँ हीप के नीचे की ओर प्रतिलिपि बनाई जाती हैं। अंततः, किसी ऑब्जेक्ट को ब्रेक टेबल द्वारा व्याप्त स्थान पर कॉपी करने की आवश्यकता होगी, जिसे अब कहीं और स्थानांतरित किया जाना चाहिए। ब्रेक टेबल के इन आंदोलनों, (लेखकों द्वारा टेबल को रोल करना कहा जाता है) के कारण स्थानांतरण रिकॉर्ड अव्यवस्थित हो जाते हैं, जिससे संघनन पूरा होने के बाद ब्रेक टेबल को क्रमबद्ध करने की आवश्यकता होती है। ब्रेक टेबल को सॉर्ट करने की लागत O(n log n) है, जहां n उन जीवित वस्तुओं की संख्या है जो एल्गोरिदम के मार्क चरण में पाई गई थीं।
अंत में, ब्रेक टेबल रिलोकेशन रिकॉर्ड का उपयोग स्थानांतरित ऑब्जेक्ट के अंदर पॉइंटर फ़ील्ड को समायोजित करने के लिए किया जाता है। पॉइंटर्स के लिए लाइव ऑब्जेक्ट की जांच की जाती है, जिसे O(log n) समय में आकार n की सॉर्ट की गई ब्रेक टेबल में देखा जा सकता है यदि ब्रेक टेबल को O(n log n) के कुल चलने वाले समय के लिए सॉर्ट किया जाता है। फिर पॉइंटर्स को स्थानांतरण तालिका में निर्दिष्ट राशि के अनुसार समायोजित किया जाता है।
एलआईएसपी 2 एल्गोरिथम
O(n log n) जटिलता से बचने के लिए, LISP 2 एल्गोरिदम हीप के ऊपर से तीन अलग-अलग पासों का उपयोग करता है। इसके अलावा, हीप वस्तुओं में एक अलग अग्रेषण सूचक स्लॉट होना चाहिए जिसका उपयोग कचरा संग्रहण के बाहर नहीं किया जाता है।
मानक अंकन के बाद, एल्गोरिथ्म निम्नलिखित तीन चरणों में आगे बढ़ता है:
- जीवित वस्तुओं के लिए अग्रेषण स्थान की गणना करें।
- एक फ्री और लाइव पॉइंटर का ट्रैक रखें और हीप की शुरुआत में दोनों को इनिशियलाइज़ करें।
- यदि लाइव पॉइंटर किसी लाइव ऑब्जेक्ट की ओर इशारा करता है, तो उस ऑब्जेक्ट के फॉरवर्डिंग पॉइंटर को वर्तमान फ्री पॉइंटर पर अपडेट करें और ऑब्जेक्ट के आकार के अनुसार फ्री पॉइंटर को बढ़ाएं।
- लाइव पॉइंटर को अगले ऑब्जेक्ट पर ले जाएं
- जब लाइव पॉइंटर हीप के अंत तक पहुंच जाए तो समाप्त करें।
- सभी पॉइंटर्स को अपडेट करें
- प्रत्येक लाइव ऑब्जेक्ट के लिए, उसके पॉइंटर्स को उन ऑब्जेक्ट्स के फॉरवर्डिंग पॉइंटर्स के अनुसार अपडेट करें जिन्हें वे इंगित करते हैं।
- वस्तुओं को स्थानांतरित करें
- प्रत्येक लाइव ऑब्जेक्ट के लिए, उसके डेटा को उसके अग्रेषित स्थान पर ले जाएं।
यह एल्गोरिदम हीप के आकार पर O(n) है; इसमें तालिका-आधारित दृष्टिकोण की तुलना में बेहतर जटिलता है, लेकिन तालिका-आधारित दृष्टिकोण का n केवल उपयोग किए गए स्थान का आकार है, न कि संपूर्ण हीप स्थान जैसा कि LISP2 एल्गोरिथ्म में है। हालाँकि, LISP2 एल्गोरिथ्म को लागू करना आसान है।
यह भी देखें
संदर्भ
- ↑ 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.
