LIFO Cache: esența, algoritmul stivei și cum funcționează

Ce este LIFO Cache?

LIFO Cache (Last In First Out Cache) — este un cache de dimensiune limitată, implementat pe baza unei stive. La adăugarea unui element nou în cache-ul plin, cel mai proaspăt (de sus) element este ştters, iar cel nou îi ia locul. Denumirea «Last In First Out» înseamnă că elementul care a intrat ultimul în cache va fi ştters primul.

O astfel de politică diferă radical de LRU și FIFO. În timp ce LRU încearcă să păstreze cele mai actuale date (după timpul ultimului acces), iar FIFO păstrează «vârsta» datelor, LIFO sacrifică în mod conştient datele proaspete. Acest lucru poate părea ilogic pentru cache, dar pentru anumite scenarii LIFO se dovedeşte a fi soluția optimă.

Implementarea clasică LIFO Cache utilizează o stivă bazată pe matrice sau listă înlănțuită. Matricea asigură stocare compactă și localitate cache, dar necesită alocare prealabilă de memorie pentru maxSize. Lista înlănțuită este mai flexibilă, dar fiecare element necesită memorie suplimentară pentru pointeri (8–16 octeți pe element).

Operațiile de bază LIFO Cache

Operația push(value) adaugă un element pe vârful stivei. Dacă dimensiunea a atins maxSize, înainte de inserare vârful este ştters. Operația pop() ştterge și returnează elementul de sus — utilă pentru scenarii de «anulare a ultimei acțiuni». Operația peek() returnează elementul de sus fără şttergere — pentru vizualizarea ultimei stări salvate fără modificarea stivei.

Cum funcționează LIFO Cache

Principiul de funcționare LIFO Cache este extrem de simplu: toate operațiile se execută cu un singur capăt al structurii — vârful stivei. La adăugarea unui element nou, acesta este plasat pe vârf. Dacă stiva este plină, elementul de sus este împins (eliminat), iar cel nou îi ia locul. Eliminarea afectează întotdeauna doar un element — vârful, deci algoritmul nu necesită parcurgere sau căutare.

Această proprietate face LIFO Cache cel mai rapid dintre toate politicile de eliminare: toate operațiile se execută în O(1) fără structuri de date suplimentare. Nu este nevoie de tabelă hash pentru căutare, nu este nevoie de listă dublu înlănțuită pentru rearanjare — este suficient un simplu pointer la vârful stivei. Memoria este consumată minim: doar pentru stocarea elementelor în sine.

Cu toate acestea, simplitatea are și o față negativă: LIFO Cache nu ia în considerare frecvența sau timpul ultimului acces la date. Dacă aplicația solicită mai întâi datele A, B, C, iar apoi din nou A — la debordare va fi eliminat C (ultimul adăugat), chiar dacĄ A nu mai este actual. Pentru scenarii de cache general acest lucru face LIFO cea mai proastă alegere, deoarece datele proaspete sunt adesea cele mai valoroase.

Dimensiunea stivei și gestionarea memoriei

Pentru LIFO Cache bazat pe matrice, dimensiunea este stabilită la creare și nu se modifică dinamic. Dacă stiva este plină și are loc push — elementul de sus este suprascris. Pentru implementarea pe listă înlănțuită, memoria este alocată pentru fiecare element la nevoie, dar la atingerea limitei, nodul vechi este deconectat și poate fi colectat de garbage collector. În aplicațiile mobile se recomandă utilizarea matricei pentru LIFO Cache, deoarece nu creează sarcină suplimentară asupra GC.

LIFO vs LRU și FIFO: compararea strategiilor

Alegerea strategiei de eliminare influențează direct eficiența cache-ului. LIFO, LRU și FIFO reprezintă abordări diferite la aceeași întrebare: ce element să eliminăm la debordare? Fiecare abordare este optimă pentru clasa sa de sarcini.

LRU oferă de obicei cel mai bun hit-ratio, dar necesită mai multă memorie și este mai complex de implementat. FIFO — compromis între performanță și hit-ratio, util pentru date de flux. LIFO — cel mai simplu, dar cu hit-ratio scăzut: trebuie aplicat doar atunci când semantica «ultimul venit – primul plecat» corespunde logicii de afaceri (navigare, anularea operațiilor).

Unde se aplică LIFO Cache

În ciuda adecvării limitate pentru cache general, LIFO Cache își găsește aplicare în scenarii concrete unde ordinea procesării datelor este inversă ordinii de sosire. Să analizăm cazurile principale.

Stive de navigare

În aplicațiile mobile se utilizează stiva de navigare: la deschiderea unui nou ecran, acesta este plasat pe vârful stivei, la apăsarea «Înapoi» — eliminat. Dacă se limitează adâncimea stivei (de exemplu, maximum 10 ecrane), LIFO Cache va elimina automat ultimul ecran la depășirea limitei. Acest lucru permite controlarea consumului de memorie al stivei de navigare fără pierderea ecranelor deschise anterior.

Stive Undo/Redo

Mecanismul de anulare a acțiunilor (Undo) — exemplu clasic LIFO. Fiecare acțiune a utilizatorului este salvată în stivă. La apelarea Undo, ultima acțiune este anulată și mutată în stiva Redo. Limitarea dimensiunii stivelor prin LIFO Cache garantează că la depășirea limitei, cele mai vechi acțiuni (la fundul stivei) rămân, iar cele mai noi sunt eliminate — ceea ce este logic, deoarece utilizatorul anulează de obicei acțiunile recente, iar cele vechi nu mai sunt actuale.

Memorarea calculelor temporare

La calcule recursive cu revenire (backtracking), rezultatele pașilor intermediari sunt salvate în ordine LIFO. Când buffer-ul se debordează, ultimul rezultat este eliminat — acest lucru este acceptabil, deoarece algoritmul îl poate recalcula la nevoie. Această abordare este utilizată în analizatoare sintactice, compilatoare și algoritmi de traversare a grafului cu limitare de adâncime.

Exemple de cod LIFO Cache

Să analizăm implementarea LIFO Cache în Kotlin utilizând o matrice de dimensiune fixă. Matricea asigură cea mai bună performanță și consum minim de memorie pentru dispozitive mobile.

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--  // elimină cel mai vechi când este plin
        }
        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]
    }
}

Indexul top indică vârful stivei. push incrementează top și scrie valoarea; dacă matricea este plină (top == maxSize - 1), înainte de scriere top este decrementat — vârful stivei este suprascris, ceea ce implementează eliminarea LIFO. Metoda pop returnează elementul și decrementează top, iar peek citește pur și simplu elementul de sus fără a modifica stiva.

Exemplu: stivă de navigare cu LIFO Cache

Să analizăm utilizarea LIFO Cache pentru limitarea adâncimii navigării în Jetpack Compose. La deschiderea unui nou ecran, acesta este adăugat în stivă, iar la depășirea limitei, cel mai recent ecran este eliminat.

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

În acest exemplu, NavigationStack utilizează LIFO Cache pentru stocarea istoricului ecranelor. La apelarea navigateTo, ecranul este adăugat în stivă, la goBack — ultimul este ştters. Dacă utilizatorul a deschis 11 ecrane cu limita 10, cel mai recent (al 11-lea) îl va elimina pe precedentul (al 10-lea) — primul ecran rămâne în stivă, ceea ce corespunde așteptărilor utilizatorului la revenire. Această strategie este mai eficientă decât LRU pentru navigare: eliminarea ecranelor deschise demult («principală», «profil») ar duce la un comportament neașteptat.