LIFO Cache: mohiyati, stek algoritmi va qanday ishlaydi

LIFO Cache nima?

LIFO Cache (Last In First Out Cache) — stek asosida amalga oshirilgan cheklangan hajmdagi keshdir. To'liq keshga yangi element qo'shilganda eng yangi (yuqori) element o'chiriladi va yangi element uning o'rnini egallaydi. «Last In First Out» nomi keshga eng oxirgi kirgan element eng birinchi o'chirilishini anglatadi.

Bunday siyosat LRU va FIFO dan tubdan farq qiladi. LRU eng dolzarb ma'lumotlarni (oxirgi murojaat vaqtiga ko'ra) saqlashga harakat qilganda, FIFO ma'lumotlarning «yoshi» ni saqlaydi, LIFO esa ataylab yangi ma'lumotlarni qurbon qiladi. Bu keshlash uchun mantiqsiz tuyulishi mumkin, ammo ma'lum stsenariylarda LIFO optimal yechim bo'lib chiqadi.

Klassik LIFO Cache amali massiv yoki bog'langan ro'yxat asosidagi stekdan foydalanadi. Massiv ixcham saqlash va kesh mahalliyligini ta'minlaydi, lekin maxSize uchun oldindan xotira ajratishni talab qiladi. Bog'langan ro'yxat moslashuvchanroq, lekin har bir element ko'rsatkichlar uchun qo'shimcha xotira talab qiladi (har bir element uchun 8–16 bayt).

LIFO Cache ning asosiy operatsiyalari

push(value) operatsiyasi elementni stekning tepasiga qo'shadi. Hajmi maxSize ga yetgan bo'lsa, qo'shishdan oldin tepa o'chiriladi. pop() operatsiyasi yuqori elementni o'chiradi va qaytaradi — «oxirgi amalni bekor qilish» stsenariylari uchun foydali. peek() operatsiyasi yuqori elementni o'chirmasdan qaytaradi — stekni o'zgartirmasdan oxirgi saqlangan holatni ko'rish uchun.

LIFO Cache qanday ishlaydi

LIFO Cache ning ishlash printsipi juda sodda: barcha operatsiyalar strukturaning bir uchida — stekning tepasida bajariladi. Yangi element qo'shilganda u tepaga joylashtiriladi. Agar stek to'la bo'lsa, yuqori element itarib chiqariladi (o'chiriladi) va yangi element uning o'rnini egallaydi. Siqib chiqarish har doim faqat bitta elementga — tepaga ta'sir qiladi, shuning uchun algoritm qidirish yoki saralashni talab qilmaydi.

Bu xususiyat LIFO Cache ni barcha siqib chiqarish siyosatlari orasida eng tezkor qiladi: barcha operatsiyalar hech qanday qo'shimcha ma'lumot tuzilmalarisiz O(1) vaqtida bajariladi. Qidirish uchun xesh-jadval, qayta tartiblash uchun ikki tomonlama bog'langan ro'yxat kerak emas — stekning tepasiga oddiy ko'rsatkich yetarli. Xotira minimal sarflanadi: faqat elementlarning o'zini saqlash uchun.

Biroq soddalikning salbiy tomoni ham bor: LIFO Cache ma'lumotlarga murojaat chastotasi yoki oxirgi murojaat vaqtini hisobga olmaydi. Agar dastur avval A, B, C ma'lumotlarini, so'ngra yana A ni so'rasa — to'lib ketganda C (oxirgi qo'shilgan) o'chiriladi, hatto A endi dolzarb bo'lmasa ham. Umumiy keshlash stsenariylari uchun bu LIFO ni eng yomon tanlovga aylantiradi, chunki yangi ma'lumotlar ko'pincha eng qimmatlidir.

Stek hajmi va xotira boshqaruvi

Massiv asosidagi LIFO Cache uchun hajm yaratilish vaqtida belgilanadi va dinamik o'zgarmaydi. Agar stek to'la bo'lsa va push sodir bo'lsa — yuqori element ustiga yoziladi. Bog'langan ro'yxatdagi amalda har bir element uchun xotira kerak bo'lganda ajratiladi, lekin limitga yetilganda eski tugun ajratiladi va axlat yig'uvchi tomonidan to'planishi mumkin. Mobil ilovalarda LIFO Cache uchun massivdan foydalanish tavsiya etiladi, chunki u GC ga qo'shimcha yuk yaratmaydi.

LIFO vs LRU va FIFO: strategiyalarni taqqoslash

Siqib chiqarish strategiyasini tanlash keshlash samaradorligiga bevosita ta'sir qiladi. LIFO, LRU va FIFO bitta savolga turli yondashuvlarni ifodalaydi: to'lib ketganda qaysi elementni o'chirish kerak? Har bir yondashuv o'z vazifalar sinfi uchun optimaldir.

LRU odatda eng yaxshi hit-ratio beradi, lekin ko'proq xotira va murakkabroq amal talab qiladi. FIFO — samaradorlik va hit-ratio o'rtasida murosadir, oqim ma'lumotlari uchun foydali. LIFO — eng sodda, ammo past hit-ratio bilan: uni faqat «oxirgi kelgan — birinchi chiqadi» semantikasi biznes mantiqiga mos kelganda qo'llash kerak (navigatsiya, operatsiyalarni bekor qilish).

LIFO Cache qayerda qo'llaniladi

Umumiy keshlash uchun cheklangan yaroqliligiga qaramasdan, LIFO Cache ma'lumotlarni qayta ishlash tartibi qabul qilish tartibiga teskari bo'lgan aniq stsenariylarda qo'llaniladi. Asosiy holatlarni ko'rib chiqaylik.

Navigatsiya steklari

Mobil ilovalarda navigatsiya stekidan foydalaniladi: yangi ekran ochilganda u stekning tepasiga joylashtiriladi, «Orqaga» tugmasi bosilganda olib tashlanadi. Agar stek chuqurligi cheklansa (masalan, maksimal 10 ekran), LIFO Cache limitdan oshganda avtomatik ravishda eng oxirgi ekranni o'chiradi. Bu avval ochilgan ekranlarni yo'qotmasdan navigatsiya stekining xotira sarfini boshqarish imkonini beradi.

Undo/Redo steklari

Amallarni bekor qilish mexanizmi (Undo) — LIFO ning klassik namunasidir. Foydalanuvchining har bir amali stekda saqlanadi. Undo chaqirilganda oxirgi amal bekor qilinadi va Redo stekiga ko'chiriladi. LIFO Cache orqali stek hajmlarini cheklash limitdan oshganda eng eski amallar (stekning tubida) qolishini va eng yangilari tashlab yuborilishini ta'minlaydi — bu mantiqiy, chunki foydalanuvchi odatda so'nggi amallarni bekor qiladi va eskilari endi dolzarb emas.

Vaqtinchalik hisoblashlarni buferlash

Qaytish (backtracking) bilan rekursiv hisoblashlarda oraliq qadamlarning natijalari LIFO tartibida saqlanadi. Bufer to'lib ketganda oxirgi natija tashlab yuboriladi — bu maqbul, chunki algoritm kerak bo'lganda uni qayta hisoblashi mumkin. Bu yondashuv parserlarda, kompilyatorlarda va chuqurlik cheklovi bo'lgan grafikni aylanib o'tish algoritmlarida qo'llaniladi.

LIFO Cache kod namunalari

Kotlin da LIFO Cache ni o'lchami qat'iy belgilangan massiv yordamida amalga oshirishni ko'rib chiqaylik. Massiv mobil qurilmalar uchun eng yaxshi samaradorlik va minimal xotira sarfini ta'minlaydi.

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--  // to'la bo'lganda eng eskisini tashla
        }
        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 indeksi stekning tepasiga ishora qiladi. push top ni oshiradi va qiymatni yozadi; agar massiv to'la bo'lsa (top == maxSize - 1), yozishdan oldin top kamaytiriladi — stekning tepasi ustiga yoziladi, bu LIFO siqib chiqarishni amalga oshiradi. pop metodi elementni qaytaradi va top ni kamaytiradi, peek esa stekni o'zgartirmasdan yuqori elementni o'qiydi.

Misol: LIFO Cache bilan navigatsiya steki

Jetpack Compose da navigatsiya chuqurligini cheklash uchun LIFO Cache dan foydalanishni ko'rib chiqaylik. Yangi ekran ochilganda u stekga qo'shiladi va limitdan oshganda eng oxirgi ekran siqib chiqariladi.

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()
    }
}

Bu misolda NavigationStack ekranlar tarixini saqlash uchun LIFO Cache dan foydalanadi. navigateTo chaqirilganda ekran stekga qo'shiladi, goBack da esa oxirgisi o'chiriladi. Agar foydalanuvchi limit 10 bo'lgan holda 11 ekran ochsa, eng oxirgisi (11-chi) avvalgisini (10-chi) siqib chiqaradi — birinchi ekran stekda qoladi, bu orqaga qaytishda foydalanuvchi kutganiga mos keladi. Bu strategiya navigatsiya uchun LRU dan samaraliroq: allaqachon ochilgan ekranlarni («bosh sahifa», «profil») o'chirish kutilmagan xatti-harakatga olib kelardi.