LIFO Cache: جوہر، اسٹیک الگورتھم اور یہ کیسے کام کرتا ہے

LIFO Cache کیا ہے؟

LIFO Cache (Last In First Out Cache) ایک مقررہ سائز کا کیش ہے جو اسٹیک پر بنایا گیا ہے۔ جب بھرے ہوئے کیش میں ایک نیا عنصر شامل کیا جاتا ہے، تو سب سے نیا (اوپر والا) عنصر ہٹا دیا جاتا ہے اور نیا عنصر اس کی جگہ لے لیتا ہے۔ نام “Last In First Out” کا مطلب ہے کہ کیش میں سب سے آخر میں آنے والا عنصر پہلے خارج کیا جائے گا۔

یہ پالیسی LRU اور FIFO سے یکسر مختلف ہے۔ جہاں LRU سب سے زیادہ متعلقہ ڈیٹا (آخری رسائی کے وقت کے مطابق) رکھنے کی کوشش کرتا ہے اور FIFO ڈیٹا کی “عمر” محفوظ رکھتا ہے، وہیں LIFO جان بوجھ کر نئے ڈیٹا کو قربان کرتا ہے۔ یہ کیشنگ کے لیے بدیہی طور پر خلاف معلوم ہو سکتا ہے، لیکن بعض منظرناموں میں LIFO بہترین حل ثابت ہوتا ہے۔

LIFO Cache کا کلاسک نفاذ ایک صف یا منسلک فہرست پر مبنی اسٹیک استعمال کرتا ہے۔ صف کمپیکٹ ذخیرہ اور کیش مقامیت فراہم کرتی ہے لیکن maxSize کے لیے پہلے سے مختص میموری کی ضرورت ہوتی ہے۔ منسلک فہرست زیادہ لچکدار ہے، لیکن ہر عنصر کو پوائنٹرز کے لیے اضافی میموری درکار ہوتی ہے (8–16 بائٹ فی عنصر)۔

LIFO Cache کی بنیادی کارروائیاں

push(value) کارروائی اسٹیک کی چوٹی پر ایک عنصر شامل کرتی ہے۔ اگر سائز maxSize تک پہنچ جائے تو، اندراج سے پہلے چوٹی ہٹا دی جاتی ہے۔ pop() کارروائی اوپر والے عنصر کو ہٹاتی ہے اور لوٹاتی ہے — “آخری عمل کو کالعدم کریں” کے منظرناموں کے لیے مفید۔ peek() کارروائی اوپر والے عنصر کو ہٹائے بغیر لوٹاتی ہے — اسٹیک کو تبدیل کیے بغیر آخری محفوظ شدہ حالت دیکھنے کے لیے۔

LIFO Cache کیسے کام کرتا ہے

LIFO Cache کے کام کرنے کا اصول انتہائی آسان ہے: تمام کارروائیاں ڈھانچے کے ایک سرے — اسٹیک کی چوٹی پر انجام دی جاتی ہیں۔ جب ایک نیا عنصر شامل کیا جاتا ہے، تو اسے چوٹی پر رکھا جاتا ہے۔ اگر اسٹیک بھرا ہوا ہے، تو اوپر والا عنصر نکالا (ہٹایا) جاتا ہے اور نیا اس کی جگہ لے لیتا ہے۔ اخراج ہمیشہ صرف ایک عنصر — چوٹی کو متاثر کرتا ہے، اس لیے الگورتھم کو تکرار یا تلاش کی ضرورت نہیں ہوتی۔

یہ خاصیت LIFO Cache کو تمام اخراج پالیسیوں میں سب سے تیز بناتی ہے: تمام کارروائیاں بغیر کسی اضافی ڈیٹا ڈھانچے کے O(1) میں چلتی ہیں۔ تلاش کے لیے ہیش ٹیبل کی ضرورت نہیں، دوبارہ ترتیب دینے کے لیے دوہری منسلک فہرست کی نہیں — صرف اسٹیک کی چوٹی پر ایک سادہ پوائنٹر کافی ہے۔ میموری کی کھپت کم سے کم ہے: صرف عناصر کا ذخیرہ۔

تاہم، سادگی کا ایک منفی پہلو ہے: LIFO Cache ڈیٹا کی تعدد یا آخری رسائی کے وقت پر غور نہیں کرتا۔ اگر کوئی ایپلیکیشن پہلے ڈیٹا A، B، C اور پھر دوبارہ A کی درخواست کرتی ہے، تو C (آخری شامل کردہ) خارج ہو جائے گا جب کیش بھر جاتا ہے، چاہے A اب متعلقہ نہ ہو۔ عام کیشنگ منظرناموں کے لیے یہ LIFO کو بدترین انتخاب بناتا ہے، کیونکہ نیا ڈیٹا اکثر سب سے قیمتی ہوتا ہے۔

اسٹیک کا سائز اور میموری کا انتظام

صف پر مبنی LIFO Cache کے لیے، سائز تخلیق کے وقت مقرر کیا جاتا ہے اور متحرک طور پر تبدیل نہیں ہوتا۔ اگر اسٹیک بھرا ہوا ہے اور push ہوتا ہے، تو اوپر والے عنصر کو اوور رائٹ کر دیا جاتا ہے۔ منسلک فہرست کے نفاذ کے لیے، ضرورت کے مطابق فی عنصر میموری مختص کی جاتی ہے، لیکن حد پہنچنے پر پرانا نوڈ منقطع ہو جاتا ہے اور کوڑا کرکٹ جمع کرنے والے کے ذریعے جمع کیا جا سکتا ہے۔ موبائل ایپلیکیشنز میں LIFO Cache کے لیے صف استعمال کرنے کی سفارش کی جاتی ہے، کیونکہ یہ GC پر اضافی بوجھ نہیں ڈالتی۔

LIFO بمقابلہ LRU اور FIFO: حکمت عملی کا موازنہ

اخراج کی حکمت عملی کا انتخاب براہ راست کیشنگ کی کارکردگی کو متاثر کرتا ہے۔ LIFO، LRU اور FIFO ایک ہی سوال کے مختلف طریقوں کی نمائندگی کرتے ہیں: کیش بھرنے پر کون سا عنصر ہٹایا جائے؟ ہر طریقہ اپنی مخصوص قسم کے کاموں کے لیے بہترین ہے۔

LRU عام طور پر بہترین ہٹ کی شرح فراہم کرتا ہے لیکن اسے زیادہ میموری کی ضرورت ہوتی ہے اور نفاذ زیادہ پیچیدہ ہے۔ FIFO کارکردگی اور ہٹ کی شرح کے درمیان ایک سمجھوتہ ہے، سٹریمنگ ڈیٹا کے لیے مفید۔ LIFO سب سے آسان ہے لیکن کم ہٹ کی شرح کے ساتھ: اسے صرف اس وقت استعمال کیا جانا چاہیے جب “آخری آیا، پہلے گیا” کا مفہوم کاروباری منطق (نیویگیشن، انڈو آپریشنز) سے مطابقت رکھتا ہو۔

LIFO Cache کہاں استعمال ہوتا ہے

عام کیشنگ کے لیے محدود موزوں ہونے کے باوجود، LIFO Cache مخصوص منظرناموں میں استعمال پایا جاتا ہے جہاں ڈیٹا پروسیسنگ کی ترتیب آمد کی ترتیب کے برعکس ہوتی ہے۔ آئیے اہم معاملات پر غور کریں۔

نیویگیشن اسٹیک

موبائل ایپلیکیشنز میں، ایک نیویگیشن اسٹیک استعمال کیا جاتا ہے: جب ایک نئی اسکرین کھولی جاتی ہے، تو اسے اسٹیک کی چوٹی پر رکھا جاتا ہے؛ جب “واپس” بٹن دبایا جاتا ہے، تو اسے ہٹا دیا جاتا ہے۔ اگر اسٹیک کی گہرائی محدود ہے (مثال کے طور پر، زیادہ سے زیادہ 10 اسکرینیں)، تو LIFO Cache حد سے تجاوز کرنے پر خود بخود تازہ ترین اسکرین کو خارج کر دے گا۔ یہ آپ کو پہلے سے کھلی اسکرینوں کو کھوئے بغیر نیویگیشن اسٹیک کی میموری کھپت کو کنٹرول کرنے کی اجازت دیتا ہے۔

انڈو/ریڈو اسٹیک

انڈو میکانزم (Undo) LIFO کی ایک کلاسک مثال ہے۔ ہر صارف کی کارروائی ایک اسٹیک میں محفوظ کی جاتی ہے۔ جب Undo کو بلایا جاتا ہے، تو آخری کارروائی کالعدم کی جاتی ہے اور ریڈو اسٹیک میں منتقل کر دی جاتی ہے۔ LIFO Cache کے ذریعے اسٹیک کے سائز کو محدود کرنا یقینی بناتا ہے کہ جب حد سے تجاوز ہو جائے، سب سے پرانی کارروائیاں (اسٹیک کے نیچے) باقی رہیں جبکہ تازہ ترین کارروائیاں ضائع ہو جائیں — جو منطقی ہے کیونکہ صارف عام طور پر حالیہ کارروائیوں کو کالعدم کرتا ہے جبکہ پرانی کارروائیاں مزید متعلقہ نہیں ہوتیں۔

عارضی حساب بفرنگ

بیک ٹریکنگ کے ساتھ تکراری حسابات میں، درمیانی مراحل کے نتائج LIFO ترتیب میں محفوظ کیے جاتے ہیں۔ جب بفر اوور فلو ہوتا ہے، آخری نتیجہ ضائع کر دیا جاتا ہے — یہ قابل قبول ہے کیونکہ الگورتھم ضرورت پڑنے پر دوبارہ حساب کر سکتا ہے۔ یہ طریقہ پارسرز، کمپائلرز اور گہرائی کی حد کے ساتھ گراف ٹراورسل الگورتھم میں استعمال ہوتا ہے۔

LIFO Cache کوڈ کی مثالیں

آئیے ایک مقررہ سائز کی صف استعمال کرتے ہوئے Kotlin میں LIFO Cache کے نفاذ کو دیکھیں۔ صف موبائل آلات کے لیے بہترین کارکردگی اور کم سے کم میموری کھپت فراہم کرتی ہے۔

class LifoCache<V>(
    private val maxSize: Int
) {
    private val array = arrayOfNulls<V>(maxSize)
    private var top = -1

    fun push(value: V) {
        if (top == maxSize - 1) {
            top--  // discard oldest when full
        }
        array[++top] = value
    }

    fun pop(): V? {
        if (top == -1) return null
        val result = array[top]
        array[top--] = null
        return result
    }

    fun peek(): V? {
        return array[top]
    }
}

انڈیکس top اسٹیک کی چوٹی کی طرف اشارہ کرتا ہے۔ push top کو بڑھاتا ہے اور قدر لکھتا ہے؛ اگر صف بھری ہوئی ہے (top == maxSize - 1)، تو لکھنے سے پہلے top کو گھٹایا جاتا ہے — اسٹیک کی چوٹی اوور رائٹ ہو جاتی ہے، جو LIFO اخراج کو نافذ کرتا ہے۔ pop طریقہ عنصر لوٹاتا ہے اور top کو گھٹاتا ہے، جبکہ peek اسٹیک کو تبدیل کیے بغیر اوپر والا عنصر پڑھتا ہے۔

مثال: LIFO Cache کے ساتھ نیویگیشن اسٹیک

Jetpack Compose میں نیویگیشن گہرائی کو محدود کرنے کے لیے LIFO Cache کے استعمال پر غور کریں۔ جب ایک نئی اسکرین کھولی جاتی ہے، تو اسے اسٹیک میں شامل کیا جاتا ہے، اور جب حد سے تجاوز ہوتا ہے، تازہ ترین اسکرین خارج کر دی جاتی ہے۔

class NavigationStack(maxDepth: Int = 10) {
    private val cache = LifoCache<Screen>(maxDepth)

    fun navigateTo(screen: Screen) {
        cache.push(screen)
    }

    fun goBack(): Screen? {
        return cache.pop()
    }

    fun currentScreen(): Screen? {
        return cache.peek()
    }
}

اس مثال میں، NavigationStack اسکرین کی تاریخ محفوظ کرنے کے لیے LIFO Cache استعمال کرتا ہے۔ جب navigateTo بلایا جاتا ہے، اسکرین اسٹیک میں شامل ہو جاتی ہے؛ جب goBack بلایا جاتا ہے، آخری اسکرین ہٹا دی جاتی ہے۔ اگر صارف نے 10 کی حد کے ساتھ 11 اسکرینیں کھولی ہیں، تو تازہ ترین (11ویں) پچھلی (10ویں) کو خارج کر دے گی — پہلی اسکرین اسٹیک میں رہتی ہے، جو واپس جاتے وقت صارف کی توقعات سے مطابقت رکھتی ہے۔ یہ حکمت عملی نیویگیشن کے لیے LRU سے زیادہ موثر ہے: دیر سے کھلی اسکرینوں (“ہوم”، “پروفائل”) کو ہٹانا غیر متوقع رویے کا باعث بنے گا۔