LIFO Cache: istota, algorytm stosu i jak działa

Czym jest LIFO Cache?

LIFO Cache (Last In First Out Cache) — to pamięć podręczna o ograniczonym rozmiarze, zaimplementowana na bazie stosu. Podczas dodawania nowego elementu do pełnej pamięci podręcznej usuwany jest najświeższy (górny) element, a nowy zajmuje jego miejsce. Nazwa «Last In First Out» oznacza, że element, który trafił do pamięci podręcznej jako ostatni, zostanie usunięty jako pierwszy.

Taka polityka radykalnie różni się od LRU i FIFO. Podczas gdy LRU próbuje zachować najbardziej aktualne dane (według czasu ostatniego dostępu), a FIFO zachowuje «wiek» danych, LIFO świadomie poświęca świeże dane. Może się to wydawać nielogiczne dla buforowania, ale w pewnych scenariuszach LIFO okazuje się optymalnym rozwiązaniem.

Klasyczna implementacja LIFO Cache wykorzystuje stos oparty na tablicy lub liście powiązanej. Tablica zapewnia kompaktowe przechowywanie i lokalność pamięci podręcznej, ale wymaga wcześniejszego przydzielenia pamięci dla maxSize. Lista powiązana jest bardziej elastyczna, ale każdy element wymaga dodatkowej pamięci na wskaźniki (8–16 bajtów na element).

Podstawowe operacje LIFO Cache

Operacja push(value) dodaje element na wierzchołek stosu. Jeśli rozmiar osiągnął maxSize, przed wstawieniem wierzchołek jest usuwany. Operacja pop() usuwa i zwraca górny element — przydatne w scenariuszach «cofnięcia ostatniej akcji». Operacja peek() zwraca górny element bez usuwania — do podglądu ostatniego zapisanego stanu bez zmiany stosu.

Jak działa LIFO Cache

Zasada działania LIFO Cache jest niezwykle prosta: wszystkie operacje wykonywane są na jednym końcu struktury — wierzchołku stosu. Podczas dodawania nowego elementu jest on umieszczany na wierzchołku. Jeśli stos jest pełny, górny element jest wypychany (usuwany), a nowy zajmuje jego miejsce. Usunięcie zawsze dotyczy tylko jednego elementu — wierzchołka, więc algorytm nie wymaga przeglądania ani wyszukiwania.

Ta właściwość czyni LIFO Cache najszybszym spośród wszystkich polityk usuwania: wszystkie operacje wykonywane są w O(1) bez jakichkolwiek dodatkowych struktur danych. Nie potrzebna jest tabela mieszająca do wyszukiwania, nie potrzebna jest lista dwukierunkowa do przestawiania — wystarczy prosty wskaźnik na wierzchołek stosu. Pamięć jest zużywana minimalnie: tylko na przechowywanie samych elementów.

Jednak prostota ma swoją wadę: LIFO Cache nie uwzględnia częstotliwości ani czasu ostatniego dostępu do danych. Jeśli aplikacja najpierw żąda danych A, B, C, a następnie ponownie A — przy przepełnieniu zostanie usunięte C (ostatnio dodane), nawet jeśli A nie jest już aktualne. Dla scenariuszy ogólnego buforowania czyni to LIFO najgorszym wyborem, ponieważ świeże dane są często najbardziej wartościowe.

Rozmiar stosu i zarządzanie pamięcią

Dla LIFO Cache opartego na tablicy rozmiar jest ustawiany przy tworzeniu i nie zmienia się dynamicznie. Jeśli stos jest pełny i następuje push — górny element jest nadpisywany. Dla implementacji na liście powiązanej pamięć jest przydzielana dla każdego elementu w miarę potrzeby, ale po osiągnięciu limitu stary węzeł jest odłączany i może zostać zebrany przez garbage collector. W aplikacjach mobilnych zaleca się używanie tablicy dla LIFO Cache, ponieważ nie powoduje ona dodatkowego obciążenia GC.

LIFO vs LRU i FIFO: porównanie strategii

Wybór strategii usuwania bezpośrednio wpływa na efektywność buforowania. LIFO, LRU i FIFO reprezentują różne podejścia do jednego pytania: który element usunąć przy przepełnieniu. Każde podejście jest optymalne dla swojej klasy zadań.

LRU zazwyczaj daje najlepszy hit-ratio, ale wymaga więcej pamięci i jest trudniejszy w implementacji. FIFO — kompromis między wydajnością a hit-ratio, przydatny dla danych strumieniowych. LIFO — najprostszy, ale z niskim hit-ratio: należy go stosować tylko wtedy, gdy semantyka «ostatni przyszedł — pierwszy wyszedł» odpowiada logice biznesowej (nawigacja, cofanie operacji).

Gdzie stosuje się LIFO Cache

Pomimo ograniczonej przydatności do ogólnego buforowania, LIFO Cache znajduje zastosowanie w konkretnych scenariuszach, gdzie kolejność przetwarzania danych jest odwrotna do kolejności napływu. Rozważmy główne przypadki.

Stosy nawigacyjne

W aplikacjach mobilnych używany jest stos nawigacji: podczas otwierania nowego ekranu jest on umieszczany na wierzchołku stosu, po naciśnięciu «Wstecz» — zdejmowany. Jeśli ograniczyć głębokość stosu (na przykład maksymalnie 10 ekranów), LIFO Cache będzie automatycznie usuwać najnowszy ekran po przekroczeniu limitu. Pozwala to kontrolować zużycie pamięci przez stos nawigacyjny bez utraty wcześniej otwartych ekranów.

Stosy Undo/Redo

Mechanizm cofania akcji (Undo) — klasyczny przykład LIFO. Każda akcja użytkownika jest zapisywana w stosie. Przy wywołaniu Undo ostatnia akcja jest cofana i przenoszona do stosu Redo. Ograniczenie rozmiaru stosów za pomocą LIFO Cache gwarantuje, że po przekroczeniu limitu najstarsze akcje (na dnie stosu) pozostaną, a najnowsze zostaną odrzucone — co jest logiczne, ponieważ użytkownik zazwyczaj cofa niedawne akcje, a stare nie są już aktualne.

Buforowanie obliczeń tymczasowych

Przy rekurencyjnych obliczeniach z powrotem (backtracking) wyniki pośrednich kroków są zapisywane w kolejności LIFO. Gdy bufor się przepełnia, ostatni wynik jest odrzucany — jest to dopuszczalne, ponieważ algorytm może go przeliczyć w razie potrzeby. Takie podejście jest stosowane w parserach, kompilatorach i algorytmach przeszukiwania grafów z ograniczeniem głębokości.

Przykłady kodu LIFO Cache

Rozważmy implementację LIFO Cache w Kotlin z użyciem tablicy o stałym rozmiarze. Tablica zapewnia najlepszą wydajność i minimalne zużycie pamięci dla urządzeń mobilnych.

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--  // usuń najstarszy, gdy pełny
        }
        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]
    }
}

Indeks top wskazuje na wierzchołek stosu. push zwiększa top i zapisuje wartość; jeśli tablica jest pełna (top == maxSize - 1), przed zapisem top jest zmniejszany — wierzchołek stosu jest nadpisywany, co realizuje usuwanie LIFO. Metoda pop zwraca element i zmniejsza top, a peek po prostu odczytuje górny element bez zmiany stosu.

Przykład: stos nawigacyjny z LIFO Cache

Rozważmy użycie LIFO Cache do ograniczenia głębokości nawigacji w Jetpack Compose. Podczas otwierania nowego ekranu jest on dodawany do stosu, a po przekroczeniu limitu najpóźniejszy ekran jest usuwany.

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

W tym przykładzie NavigationStack używa LIFO Cache do przechowywania historii ekranów. Przy wywołaniu navigateTo ekran jest dodawany do stosu, przy goBack — usuwany jest ostatni. Jeśli użytkownik otworzył 11 ekranów przy limicie 10, najpóźniejszy (11.) zastąpi poprzedni (10.) — pierwszy ekran pozostanie w stosie, co odpowiada oczekiwaniom użytkownika przy powrocie. Taka strategia jest skuteczniejsza niż LRU dla nawigacji: usunięcie dawno otwartych ekranów («strona główna», «profil») prowadziłoby do nieoczekiwanego zachowania.