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 কল করা হয়, শেষ কাজটি পূর্বাবস্থায় ফেরানো হয় এবং Redo স্ট্যাকে সরানো হয়। 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-এর চেয়ে বেশি কার্যকর: দীর্ঘদিন ধরে খোলা স্ক্রিন (“হোম”, “প্রোফাইল”) সরানো অপ্রত্যাশিত আচরণের দিকে নিয়ে যাবে।