Mark–compact algorithm
કોમ્પ્યુટર વિજ્ઞાનમાં, માર્ક-કોમ્પેક્ટ અલ્ગોરિધમ એ કચરો સંગ્રહ અલ્ગોરિધમનો એક પ્રકાર છે જેનો ઉપયોગ પહોંચી ન શકાય તેવી મેમરીને ફરીથી મેળવવા માટે થાય છે. માર્ક-કોમ્પેક્ટ અલ્ગોરિધમ્સને માર્ક-સ્વીપ અલ્ગોરિધમ અને ચેનીના કોપી અલ્ગોરિધમના સંયોજન તરીકે ગણી શકાય. પ્રથમ, પહોંચી શકાય તેવી વસ્તુઓને ચિહ્નિત કરવામાં આવે છે, પછી કોમ્પેક્ટિંગ પગલું પહોંચી શકાય તેવી (ચિહ્નિત) વસ્તુઓને ઢગલાના વિસ્તારની શરૂઆત તરફ સ્થાનાંતરિત કરે છે. કોમ્પેક્ટિંગ કચરો સંગ્રહનો ઉપયોગ આધુનિક જેવીએમ, માઇક્રોસોફ્ટના કોમન લેંગ્વેજ રનટાઇમ અને ગ્લાસગો હાસ્કેલ કમ્પાઇલર દ્વારા થાય છે. અલ્ગોરિધમ્સ જીવંત પદાર્થોને ઢગલામાં માર્ક-સ્વીપ અલ્ગોરિધમ જેવી જ રીતે ચિહ્નિત કર્યા પછી, ઢગલાને ઘણીવાર વિભાજિત કરવામાં આવશે. માર્ક-કોમ્પેક્ટ એલ્ગોરિધમ્સનો ધ્યેય મેમરીમાં જીવંત પદાર્થોને એકસાથે ખસેડવાનો છે જેથી ફ્રેગમેન્ટેશન દૂર થાય. પડકાર એ છે કે ખસેડેલા પદાર્થોના તમામ પોઇન્ટરને યોગ્ય રીતે અપડેટ કરવું, જેમાંથી મોટાભાગના કોમ્પેક્શન પછી નવા મેમરી સરનામાં હશે. પોઇન્ટર અપડેટ્સને સંભાળવાની સમસ્યાને વિવિધ રીતે નિયંત્રિત કરવામાં આવે છે. કોષ્ટક-આધારિત સંકલન કોષ્ટક-આધારિત અલ્ગોરિધમને સૌપ્રથમ 1967માં હેડોન અને વેઇટ દ્વારા વર્ણવવામાં આવ્યું હતું. તે ઢગલામાં જીવંત પદાર્થોના સંબંધિત સ્થાનને જાળવી રાખે છે, અને માત્ર સતત ઓવરહેડની જરૂર પડે છે. કોમ્પેક્શન ઢગલાના તળિયે (નીચા સરનામાં) થી ટોચ (ઉચ્ચ સરનામાં) સુધી આગળ વધે છે. જેમ જેમ જીવંત (એટલે કે, ચિહ્નિત) વસ્તુઓનો સામનો કરવામાં આવે છે, તેમને પ્રથમ ઉપલબ્ધ નીચલા સરનામાં પર ખસેડવામાં આવે છે, અને સ્થાનાંતરણ માહિતીના વિરામ કોષ્ટકમાં રેકોર્ડ જોડવામાં આવે છે. દરેક જીવંત ઓબ્જેક્ટ માટે, બ્રેક ટેબલમાં રેકોર્ડમાં કોમ્પેક્શન પહેલાં ઓબ્જેક્ટનું મૂળ સરનામું અને કોમ્પેક્શન પછી મૂળ સરનામું અને નવા સરનામાં વચ્ચેનો તફાવત હોય છે. બ્રેક ટેબલ એ ઢગલામાં સંગ્રહિત કરવામાં આવે છે જે કોમ્પેક્ટ કરવામાં આવી રહ્યું છે, પરંતુ તે વિસ્તારમાં કે જે બિનઉપયોગી તરીકે ચિહ્નિત થયેલ છે. કોમ્પેક્શન હંમેશાં સફળ થાય તે સુનિશ્ચિત કરવા માટે, ઢગલામાં ઓછામાં ઓછું ઓબ્જેક્ટનું કદ બ્રેક ટેબલ રેકોર્ડ કરતા મોટું અથવા તે જ કદનું હોવું જોઈએ. જેમ જેમ સંકોચન આગળ વધે છે તેમ, સ્થાનાંતરિત પદાર્થોને ઢગલાના તળિયે નકલ કરવામાં આવે છે. આખરે ઑબ્જેક્ટને બ્રેક ટેબલ દ્વારા કબજે કરેલી જગ્યામાં નકલ કરવાની જરૂર પડશે, જે હવે અન્યત્ર સ્થાનાંતરિત થવી જોઈએ. બ્રેક ટેબલની આ હિલચાલ, (લેખકો દ્વારા ટેબલને રોલિંગ કહેવામાં આવે છે) સ્થળાંતરના રેકોર્ડ્સને અવ્યવસ્થિત બનાવે છે, સંકોચન પૂર્ણ થયા પછી બ્રેક ટેબલને સૉર્ટ કરવાની જરૂર પડે છે. બ્રેક ટેબલને સૉર્ટ કરવાની કિંમત ઓ (એન લોગ એન) છે, જ્યાં એન એ જીવંત પદાર્થોની સંખ્યા છે જે અલ્ગોરિધમના માર્ક તબક્કામાં મળી આવી હતી. છેવટે, બ્રેક ટેબલ રીલોકેશન રેકોર્ડ્સનો ઉપયોગ સ્થાનાંતરિત વસ્તુઓની અંદર પોઇન્ટર ક્ષેત્રોને સમાયોજિત કરવા માટે થાય છે. જીવંત પદાર્થોની પોઇન્ટર માટે તપાસ કરવામાં આવે છે, જે ઓ (એન લોગ એન) ના કુલ ચાલતા સમય માટે, જો બ્રેક ટેબલને સૉર્ટ કરવામાં આવે તો ઓ (એન લોગ એન) સમયમાં કદ એનના સૉર્ટ કરેલા બ્રેક ટેબલમાં જોઈ શકાય છે. પોઇન્ટર પછી સ્થળાંતર કોષ્ટકમાં નિર્દિષ્ટ રકમ દ્વારા ગોઠવવામાં આવે છે. LISP 2 અલ્ગોરિધમ ઓ (એન લોગ એન) જટિલતાને ટાળવા માટે, અલ્ગોરિધમ ઢગલા પર ત્રણ અલગ અલગ પાસનો ઉપયોગ કરે છે. વધુમાં, ઢગલાબંધ વસ્તુઓમાં એક અલગ ફોરવર્ડિંગ પોઇન્ટર સ્લોટ હોવો આવશ્યક છે જેનો ઉપયોગ કચરો સંગ્રહની બહાર થતો નથી. પ્રમાણભૂત માર્કિંગ પછી, અલ્ગોરિધમ નીચેના ત્રણ પાસમાં આગળ વધે છેઃ જીવંત પદાર્થો માટે ફોરવર્ડિંગ સ્થાનની ગણતરી કરો. મફત અને જીવંત નિર્દેશક પર નજર રાખો અને ઢગલાની શરૂઆત સુધી બંનેને પ્રારંભ કરો. જો જીવંત પોઇન્ટર જીવંત ઑબ્જેક્ટ તરફ નિર્દેશ કરે છે, તો તે ઓબ્જેક્ટના ફોરવર્ડિંગ પોઇન્ટરને વર્તમાન મુક્ત પોઇન્ટર પર અપડેટ કરો અને ઓબ્જેક્ટના કદ અનુસાર મુક્ત પોઇન્ટરને વધારો. જ્યારે જીવંત નિર્દેશક ઢગલાના અંત સુધી પહોંચે ત્યારે જીવંત નિર્દેશકને આગામી ઑબ્જેક્ટ એન્ડ પર ખસેડો. દરેક જીવંત ઓબ્જેક્ટ માટે, તેઓ જે ઓબ્જેક્ટ તરફ નિર્દેશ કરે છે તેના ફોરવર્ડિંગ પોઇન્ટર અનુસાર તેના પોઇન્ટરને અપડેટ કરો. ઓબ્જેક્ટ ખસેડો દરેક જીવંત ઓબ્જેક્ટ માટે, તેના ડેટાને તેના ફોરવર્ડિંગ સ્થાન પર ખસેડો. ઢગલાના કદ પર આ અલ્ગોરિધમ O (n) છે; તે ટેબલ-આધારિત અભિગમ કરતાં વધુ સારી જટિલતા ધરાવે છે, પરંતુ ટેબલ-આધારિત અભિગમનો n એ માત્ર વપરાયેલી જગ્યાનું કદ છે, LISP2 અલ્ગોરિધમની જેમ સમગ્ર ઢગલાની જગ્યા નથી. જો કે, LISP2 અલ્ગોરિધમનો અમલ કરવો સરળ છે. ડેડ-કોડ નાબૂદી ટ્રેસિંગ કચરો સંગ્રહ સંદર્ભો ઓટોમેટિક મેમરી મેનેજમેન્ટ મેમરી મેનેજમેન્ટ અલ્ગોરિધમ્સ પણ જુઓ.