Mark–compact algorithm
کمپیوٹر سائنس میں، مارک کمپیکٹ الگورتھم ایک قسم کا کچرا جمع کرنے والا الگورتھم ہے جو ناقابل رسائی میموری کو دوبارہ حاصل کرنے کے لیے استعمال ہوتا ہے۔ مارک کمپیکٹ الگورتھم کو مارک سویپ الگورتھم اور چینی کے کاپی کرنے والے الگورتھم کا مجموعہ سمجھا جا سکتا ہے۔ سب سے پہلے، قابل رسائی اشیاء کو نشان زد کیا جاتا ہے، پھر ایک کمپیکٹنگ مرحلہ قابل رسائی (نشان زدہ) اشیاء کو ڈھیر کے علاقے کے آغاز کی طرف منتقل کرتا ہے۔ کمپیکٹنگ کچرا اکٹھا کرنا جدید جے وی ایم، مائیکروسافٹ کے کامن لینگویج رن ٹائم اور گلاسگو ہاسکل مرتب کے ذریعہ استعمال ہوتا ہے۔ الگورتھم ڈھیر میں زندہ اشیاء کو مارک سویپ الگورتھم کی طرح نشان زد کرنے کے بعد، ڈھیر اکثر ٹکڑے ٹکڑے ہو جائے گا۔ مارک کمپیکٹ الگورتھم کا مقصد میموری میں موجود زندہ اشیاء کو ایک ساتھ منتقل کرنا ہے تاکہ ٹکڑے ٹکڑے کو ختم کیا جا سکے۔ چیلنج یہ ہے کہ منتقل شدہ اشیاء کے تمام اشارے کو درست طریقے سے اپ ڈیٹ کیا جائے، جن میں سے زیادہ تر میں کمپکشن کے بعد میموری کے نئے پتے ہوں گے۔ پوائنٹر اپ ڈیٹس کو سنبھالنے کے مسئلے کو مختلف طریقوں سے نمٹا جاتا ہے۔ ٹیبل پر مبنی مرکب ایک ٹیبل پر مبنی الگورتھم سب سے پہلے 1967 میں ہیڈن اور ویٹ نے بیان کیا تھا۔ یہ ڈھیر میں زندہ اشیاء کی متعلقہ جگہ کو محفوظ رکھتا ہے، اور اس کے لیے صرف مستقل اوور ہیڈ کی ضرورت ہوتی ہے۔ کمپکشن ڈھیر کے نچلے حصے (کم پتے) سے اوپر (اونچے پتے) تک جاتا ہے۔ جیسے ہی زندہ (یعنی نشان زدہ) اشیاء کا سامنا ہوتا ہے، انہیں پہلے دستیاب کم پتے پر منتقل کر دیا جاتا ہے، اور ایک ریکارڈ کو نقل مکانی کی معلومات کے بریک ٹیبل میں شامل کیا جاتا ہے۔ ہر زندہ آبجیکٹ کے لیے، بریک ٹیبل میں ایک ریکارڈ کمپکشن سے پہلے آبجیکٹ کے اصل پتے اور کمپکشن کے بعد اصل پتے اور نئے پتے کے درمیان فرق پر مشتمل ہوتا ہے۔ بریک ٹیبل کو اس ڈھیر میں محفوظ کیا جاتا ہے جسے کمپیکٹ کیا جا رہا ہے، لیکن اس علاقے میں جو غیر استعمال شدہ کے طور پر نشان زد ہے۔ اس بات کو یقینی بنانے کے لیے کہ کمپکشن ہمیشہ کامیاب رہے گا، ڈھیر میں کم از کم آبجیکٹ کا سائز بریک ٹیبل ریکارڈ سے بڑا یا اسی سائز کا ہونا چاہیے۔ جیسے جیسے کمپکشن آگے بڑھتا ہے، منتقل شدہ اشیاء کو ڈھیر کے نچلے حصے کی طرف نقل کیا جاتا ہے۔ آخر کار کسی شے کو بریک ٹیبل کے زیر قبضہ جگہ پر نقل کرنے کی ضرورت ہوگی، جسے اب کہیں اور منتقل کرنا ہوگا۔ بریک ٹیبل کی یہ حرکتیں، (جسے مصنفین ٹیبل کو رول کرنا کہتے ہیں) نقل مکانی کے ریکارڈ کو بے ترتیب کرنے کا سبب بنتی ہیں، جس کی وجہ سے کمپکشن مکمل ہونے کے بعد بریک ٹیبل کو ترتیب دینے کی ضرورت ہوتی ہے۔ بریک ٹیبل کو ترتیب دینے کی لاگت O (n لاگ n) ہے، جہاں n زندہ اشیاء کی تعداد ہے جو الگورتھم کے مارک مرحلے میں پائی گئیں۔ آخر میں، بریک ٹیبل کی نقل مکانی کے ریکارڈ کا استعمال منتقل شدہ اشیاء کے اندر پوائنٹر فیلڈز کو ایڈجسٹ کرنے کے لیے کیا جاتا ہے۔ زندہ اشیا کی جانچ پوائنٹروں کے لیے کی جاتی ہے، جسے O (لاگ این) وقت میں سائز n کے ترتیب شدہ بریک ٹیبل میں دیکھا جا سکتا ہے اگر بریک ٹیبل کو ترتیب دیا جاتا ہے، تو O (این لاگ این) کے کل چلنے والے وقت کے لیے۔ اس کے بعد پوائنٹس کو نقل مکانی کی میز میں بیان کردہ رقم کے مطابق ایڈجسٹ کیا جاتا ہے۔ LISP 2 الگورتھم O (n لاگ n) پیچیدگی سے بچنے کے لیے، الگورتھم ڈھیر پر تین مختلف پاس استعمال کرتا ہے۔ اس کے علاوہ، ڈھیر والی اشیاء میں ایک علیحدہ فارورڈنگ پوائنٹر سلاٹ ہونا چاہیے جو کچرا جمع کرنے سے باہر استعمال نہیں ہوتا ہے۔ معیاری مارکنگ کے بعد، الگورتھم مندرجہ ذیل تین پاسوں میں آگے بڑھتا ہے: زندہ اشیاء کے لیے فارورڈنگ لوکیشن کا حساب لگائیں۔ مفت اور لائیو پوائنٹر کا سراغ لگائیں اور ڈھیر کے آغاز تک دونوں کو شروع کریں۔ اگر لائیو پوائنٹر کسی لائیو آبجیکٹ کی طرف اشارہ کرتا ہے، تو اس آبجیکٹ کے فارورڈنگ پوائنٹر کو موجودہ فری پوائنٹر پر اپ ڈیٹ کریں اور آبجیکٹ کے سائز کے مطابق فری پوائنٹر میں اضافہ کریں۔ لائیو پوائنٹر کو اگلے آبجیکٹ اینڈ پر منتقل کریں جب لائیو پوائنٹر ڈھیر کے آخر تک پہنچ جائے۔ تمام نکات کو اپ ڈیٹ کریں ہر لائیو آبجیکٹ کے لیے، اس کے نکات کو ان اشیاء کے فارورڈنگ نکات کے مطابق اپ ڈیٹ کریں جن کی طرف وہ اشارہ کرتے ہیں۔ آبجیکٹ منتقل کریں ہر زندہ آبجیکٹ کے لیے، اس کے ڈیٹا کو اس کے فارورڈنگ لوکیشن پر منتقل کریں۔ یہ الگورتھم ڈھیر کے سائز پر O (n) ہے۔ اس میں ٹیبل پر مبنی نقطہ نظر سے بہتر پیچیدگی ہے، لیکن ٹیبل پر مبنی نقطہ نظر کا n صرف استعمال شدہ جگہ کا سائز ہے، نہ کہ پوری ڈھیر کی جگہ جیسا کہ LISP2 الگورتھم میں ہے۔ تاہم، LISP2 الگورتھم کو لاگو کرنا آسان ہے۔ ڈیڈ کوڈ کے خاتمے کا سراغ لگانا کچرا جمع کرنا حوالہ جات خودکار میموری مینجمنٹ میموری مینجمنٹ الگورتھم بھی دیکھیں۔