Mark–compact algorithm
கணினி அறிவியலில், மார்க்-காம்பாக்ட் வழிமுறை என்பது அணுக முடியாத நினைவகத்தை மீட்டெடுக்கப் பயன்படுத்தப்படும் ஒரு வகை குப்பை சேகரிப்பு வழிமுறை ஆகும். மார்க்-காம்பாக்ட் வழிமுறைகள் மார்க்-ஸ்வீப் வழிமுறை மற்றும் செனியின் நகலெடுக்கும் வழிமுறை ஆகியவற்றின் கலவையாக கருதப்படலாம். முதலில், அடையக்கூடிய பொருள்கள் குறிக்கப்படுகின்றன, பின்னர் ஒரு சுருக்கமான படி குவியல் பகுதியின் தொடக்கத்தை நோக்கி அடையக்கூடிய (குறிக்கப்பட்ட) பொருட்களை இடமாற்றம் செய்கிறது. சுருக்கமான குப்பை சேகரிப்பு நவீன ஜே. வி. எம், மைக்ரோசாப்டின் காமன் லாங்குவேஜ் ரன்டைம் மற்றும் கிளாஸ்கோ ஹாஸ்கெல் கம்பைலர் ஆகியவற்றால் பயன்படுத்தப்படுகிறது. வழிமுறைகள் குவியலில் நேரடி பொருட்களை மார்க்-ஸ்வீப் அல்காரிதம் போலவே அதே பாணியில் குறித்த பிறகு, குவியல் பெரும்பாலும் துண்டுகளாக இருக்கும். மார்க்-காம்பாக்ட் வழிமுறைகளின் குறிக்கோள் நினைவகத்தில் உள்ள நேரடி பொருட்களை ஒன்றாக மாற்றுவதாகும், இதனால் துண்டு துண்டுகள் அகற்றப்படுகின்றன. நகர்த்தப்பட்ட பொருட்களுக்கு அனைத்து சுட்டிகளையும் சரியாக புதுப்பிப்பதே சவால், அவற்றில் பெரும்பாலானவை சுருக்கத்திற்குப் பிறகு புதிய நினைவக முகவரிகளைக் கொண்டிருக்கும். சுட்டிக்காட்டி புதுப்பிப்புகளைக் கையாள்வதில் உள்ள சிக்கல் வெவ்வேறு வழிகளில் கையாளப்படுகிறது. அட்டவணை அடிப்படையிலான சுருக்கம் ஒரு அட்டவணை அடிப்படையிலான வழிமுறை முதன்முதலில் 1967 இல் ஹாடன் மற்றும் வெய்ட் ஆகியோரால் விவரிக்கப்பட்டது. இது குவியலில் உயிருள்ள பொருட்களின் ஒப்பீட்டு இடத்தைப் பாதுகாக்கிறது, மேலும் நிலையான அளவு மேல்நிலை மட்டுமே தேவைப்படுகிறது. குவியலின் அடிப்பகுதியில் இருந்து (குறைந்த முகவரிகள்) மேல் (உயர் முகவரிகள்) வரை சுருக்கம் தொடர்கிறது. நேரடி (அதாவது குறிக்கப்பட்ட) பொருள்கள் எதிர்கொள்ளும்போது, அவை முதலில் கிடைக்கக்கூடிய குறைந்த முகவரிக்கு நகர்த்தப்படுகின்றன, மேலும் இடமாற்றத் தகவல்களின் இடைவெளி அட்டவணையில் ஒரு பதிவு இணைக்கப்படுகிறது. ஒவ்வொரு நேரடி பொருளுக்கும், இடைவெளி அட்டவணையில் உள்ள ஒரு பதிவு சுருக்கத்திற்கு முன் பொருளின் அசல் முகவரியையும், சுருக்கத்திற்குப் பிறகு அசல் முகவரிக்கும் புதிய முகவரிக்கும் இடையிலான வித்தியாசத்தையும் கொண்டுள்ளது. இடைவெளி அட்டவணை சுருக்கப்படும் குவியலில் சேமிக்கப்படுகிறது, ஆனால் பயன்படுத்தப்படாததாக குறிக்கப்பட்ட ஒரு பகுதியில். சுருக்கமானது எப்போதும் வெற்றிகரமாக இருக்கும் என்பதை உறுதிப்படுத்த, குவியலில் உள்ள குறைந்தபட்ச பொருள் அளவு ஒரு இடைவெளி அட்டவணை பதிவை விட பெரியதாகவோ அல்லது அதே அளவாகவோ இருக்க வேண்டும். சுருக்கம் முன்னேறும்போது, இடமாற்றம் செய்யப்பட்ட பொருள்கள் குவியலின் அடிப்பகுதியை நோக்கி நகலெடுக்கப்படுகின்றன. இறுதியில் ஒரு பொருள் இடைவெளி அட்டவணையால் ஆக்கிரமிக்கப்பட்ட இடத்திற்கு நகலெடுக்கப்பட வேண்டும், அது இப்போது வேறு இடத்திற்கு மாற்றப்பட வேண்டும். இடைவெளி அட்டவணையின் இந்த அசைவுகள், (ஆசிரியர்களால் அட்டவணையை உருட்டுவது என்று அழைக்கப்படுகிறது) இடமாற்ற பதிவுகள் ஒழுங்கற்றதாக மாற காரணமாகின்றன, சுருக்கமானது முடிந்த பிறகு இடைவெளி அட்டவணையை வரிசைப்படுத்த வேண்டும். இடைவெளி அட்டவணையை வரிசைப்படுத்துவதற்கான செலவு O (n log n) ஆகும், இதில் n என்பது வழிமுறையின் குறி கட்டத்தில் காணப்பட்ட நேரடி பொருட்களின் எண்ணிக்கை. இறுதியாக, இடமாற்றம் செய்யப்பட்ட பொருட்களுக்குள் சுட்டிக்காட்டி புலங்களை சரிசெய்ய இடைவெளி அட்டவணை இடமாற்ற பதிவுகள் பயன்படுத்தப்படுகின்றன. நேரடி பொருள்கள் சுட்டிகளுக்காக ஆராயப்படுகின்றன, அவை இடைவெளி அட்டவணை வரிசைப்படுத்தப்பட்டால், O (n log n) இன் மொத்த இயங்கும் நேரத்திற்கு O (log n) நேரத்தில் அளவு n இன் வரிசைப்படுத்தப்பட்ட இடைவெளி அட்டவணையில் பார்க்கப்படலாம். புள்ளிகள் பின்னர் இடமாற்ற அட்டவணையில் குறிப்பிடப்பட்டுள்ள தொகையால் சரிசெய்யப்படுகின்றன. LISP 2 வழிமுறை O (n log n) சிக்கலைத் தவிர்ப்பதற்காக, வழிமுறை குவியலின் மீது மூன்று வெவ்வேறு பாஸ்களைப் பயன்படுத்துகிறது. கூடுதலாக, குவியல் பொருள்கள் குப்பை சேகரிப்புக்கு வெளியே பயன்படுத்தப்படாத ஒரு தனி முன்னோக்கி சுட்டிக்காட்டி ஸ்லாட்டைக் கொண்டிருக்க வேண்டும். நிலையான குறியீட்டிற்குப் பிறகு, வழிமுறை பின்வரும் மூன்று பாஸ்களில் தொடர்கிறதுஃ நேரடி பொருட்களுக்கான முன்னோக்கி இருப்பிடத்தைக் கணக்கிடுங்கள். இலவச மற்றும் நேரடி சுட்டியைக் கண்காணித்து, குவியலின் தொடக்கம் வரை இரண்டையும் துவக்கவும். நேரடி சுட்டிக்காட்டி ஒரு நேரடி பொருளை சுட்டிக்காட்டினால், அந்த பொருளின் முன்னோக்கி சுட்டிக்காட்டியை தற்போதைய இலவச சுட்டிக்காட்டிக்கு புதுப்பித்து, பொருளின் அளவிற்கு ஏற்ப இலவச சுட்டியை அதிகரிக்கவும். நேரடி சுட்டிக்காட்டி குவியலின் முடிவை அடையும் போது நேரடி சுட்டியை அடுத்த பொருளின் முடிவுக்கு நகர்த்தவும். அனைத்து சுட்டிகளையும் புதுப்பிக்கவும் ஒவ்வொரு நேரடி பொருளுக்கும், அவை சுட்டிக்காட்டும் பொருட்களின் முன்னோக்கி சுட்டிகளுக்கு ஏற்ப அதன் சுட்டிகளை புதுப்பிக்கவும். பொருட்களை நகர்த்தவும் ஒவ்வொரு நேரடி பொருளுக்கும், அதன் தரவை அதன் முன்னோக்கி செல்லும் இடத்திற்கு நகர்த்தவும். இந்த வழிமுறை குவியலின் அளவில் O (n) ஆகும்; இது அட்டவணை அடிப்படையிலான அணுகுமுறையை விட சிறந்த சிக்கலைக் கொண்டுள்ளது, ஆனால் அட்டவணை அடிப்படையிலான அணுகுமுறையின் n என்பது பயன்படுத்தப்பட்ட இடத்தின் அளவு மட்டுமே, LISP2 வழிமுறையில் உள்ள முழு குவியல் இடமும் அல்ல. இருப்பினும், LISP2 வழிமுறை செயல்படுத்த எளிதானது. மேலும் காண்க இறந்த குறியீடு நீக்குதல் குப்பை சேகரிப்பு குறிப்புகள் தானியங்கி நினைவக மேலாண்மை நினைவக மேலாண்மை வழிமுறைகள்