LIFO Cache: podstata, algoritmus zásobníku a jak funguje

Co je LIFO Cache?

LIFO Cache (Last In First Out Cache) — je mezipaměť omezené velikosti implementovaná na základě zásobníku. Při přidání nového prvku do plné mezipaměti je nejčerstvější (nejvyšší) prvek odstraněn a nový prvek zaujme jeho místo. Název «Last In First Out» znamená, že prvek, který se dostal do mezipaměti jako poslední, bude odstraněn jako první.

Taková politika se radikálně liší od LRU a FIFO. Zatímco LRU se snaží uchovat nejaktuálnější data (podle času posledního přístupu) a FIFO zachovává «stář» dat, LIFO vědomě obětuje čerstvá data. To se může zdát nelogické pro ukládání do mezipaměti, ale pro určité scénáře se LIFO ukazuje jako optimální řešení.

Klasická implementace LIFO Cache používá zásobník založený na poli nebo propojeném seznamu. Pole poskytuje kompaktní uložení a lokalitu mezipaměti, ale vyžaduje předběžné přidělení paměti pro maxSize. Propojený seznam je flexibilnější, ale každý prvek vyžaduje dodatečnou paměť pro ukazatele (8–16 bajtů na prvek).

Základní operace LIFO Cache

Operace push(value) přidá prvek na vrchol zásobníku. Pokud velikost dosáhla maxSize, před vložením je vrchol odstraněn. Operace pop() odstraní a vrátí horní prvek — užitečné pro scénáře «zrušení poslední akce». Operace peek() vrátí horní prvek bez odstranění — pro zobrazení posledního uloženého stavu bez změny zásobníku.

Jak funguje LIFO Cache

Princip fungování LIFO Cache je mimořádně jednoduchý: všechny operace se provádějí s jedním koncem struktury — vrcholem zásobníku. Při přidání nového prvku je umístěn na vrchol. Pokud je zásobník plný, horní prvek je vytlačen (odstraněn) a nový prvek zaujme jeho místo. Vytlačení se vždy týká pouze jednoho prvku — vrcholu, takže algoritmus nevyžaduje procházení nebo vyhledávání.

Tato vlastnost dělá LIFO Cache nejrychlejším ze všech politik vytlačování: všechny operace se provádějí v O(1) bez jakýchkoli dalších datových struktur. Není potřeba hashovací tabulka pro vyhledávání, není potřeba obousměrně propojený seznam pro přeskupení — stačí jednoduchý ukazatel na vrchol zásobníku. Paměť je spotřebovávána minimálně: pouze pro uložení samotných prvků.

Jednoduchost má však i stinnou stránku: LIFO Cache nezohledňuje frekvenci nebo čas posledního přístupu k datům. Pokud aplikace nejprve požaduje data A, B, C a poté znovu A — při přetečení bude odstraněno C (naposledy přidané), i když A již není aktuální. Pro scénáře obecného ukládání do mezipaměti to dělá LIFO nejhorší volbou, protože čerstvá data jsou často nejcennější.

Velikost zásobníku a správa paměti

Pro LIFO Cache založený na poli se velikost nastavuje při vytvoření a dynamicky se nemění. Pokud je zásobník plný a dojde k push — horní prvek je přepsán. Pro implementaci na propojeném seznamu je paměť přidělována pro každý prvek podle potřeby, ale po dosažení limitu je starý uzel odpojen a může být shromážděn sběračem odpadu. V mobilních aplikacích se doporučuje použít pole pro LIFO Cache, protože nevytváří dodatečné zatížení GC.

LIFO vs LRU a FIFO: srovnání strategií

Volba strategie vytlačování přímo ovlivňuje efektivitu ukládání do mezipaměti. LIFO, LRU a FIFO představují různé přístupy ke stejné otázce: který prvek odstranit při přetečení? Každý přístup je optimální pro svou tříu úkolů.

LRU obvykle poskytuje nejlepší hit-ratio, ale vyžaduje více paměti a je složitější na implementaci. FIFO — kompromis mezi výkonem a hit-ratio, užitečný pro proudová data. LIFO — nejjednodušší, ale s nízkým hit-ratio: měl by být použit pouze tehdy, když sémantika «poslední přišel – první odešel» odpovídá obchodní logice (navigace, rušení operací).

Kde se LIFO Cache používá

Navzdory omezené vhodnosti pro obecné ukládání do mezipaměti nachází LIFO Cache uplatnění v konkrétních scénářích, kde je pořadí zpracování dat obrácené k pořadí příchodu. Podívejme se na hlavní případy.

Navigační zásobníky

V mobilních aplikacích se používá navigační zásobník: při otevření nové obrazovky je umístěna na vrchol zásobníku, při stisku tlačítka «Zpět» — odstraněna. Pokud je hloubka zásobníku omezena (například maximálně 10 obrazovek), LIFO Cache automaticky odstraní nejnovější obrazovku při překročení limitu. To umožňuje kontrolovat spotřebu paměti navigačního zásobníku bez ztráty dříve otevřených obrazovek.

Zásobníky Undo/Redo

Mechanismus zpětní akcí (Undo) — klasický příklad LIFO. Každá akce uživatele je uložena v zásobníku. Při volání Undo je poslední akce zrušena a přesunuta do zásobníku Redo. Omezení velikosti zásobníků prostřednictvím LIFO Cache zaručuje, že při překročení limitu zůstanou nejstarší akce (na dně zásobníku) a nejnovější budou odstraněny — což je logické, protože uživatel obvykle ruší nedávné akce a staré již nejsou aktuální.

Ukládání dočasných výpočtů do vyrovnávací paměti

Při rekurzivních výpočtech s návratem (backtracking) jsou výsledky mezilehlých kroků ukládány v pořadí LIFO. Když se vyrovnávací paměť přeteče, poslední výsledek je zahozen — to je přijatelné, protože algoritmus jej může v případě potřeby přepočítat. Tento přístup se používá v parserech, překladačích a algoritmech procházení grafů s omezením hloubky.

Příklady kódu LIFO Cache

Podívejme se na implementaci LIFO Cache v Kotlinu pomocí pole pevné velikosti. Pole poskytuje nejlepší výkon a minimální spotřebu paměti pro mobilní zařízení.

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--  // zahodit nejstarší, když je plno
        }
        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]
    }
}

Index top ukazuje na vrchol zásobníku. push zvyšuje top a zapisuje hodnotu; pokud je pole plné (top == maxSize - 1), před zápisem je top snížen — vrchol zásobníku je přepsán, což implementuje vytlačení LIFO. Metoda pop vrátí prvek a sníží top, zatímco peek jednoduše přečte horní prvek bez změny zásobníku.

Příklad: navigační zásobník s LIFO Cache

Podívejme se na použití LIFO Cache pro omezení hloubky navigace v Jetpack Compose. Při otevření nové obrazovky je přidána do zásobníku a při překročení limitu je nejnovější obrazovka vytlačena.

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

V tomto příkladu NavigationStack používá LIFO Cache pro ukládání historie obrazovek. Při volání navigateTo je obrazovka přidána do zásobníku, při goBack — poslední je odstraněna. Pokud uživatel otevřel 11 obrazovek s limitem 10, nejnovější (11.) vytlačí předchozí (10.) — první obrazovka zůstane v zásobníku, což odpovídá očekávání uživatele při návratu. Tato strategie je účinnější než LRU pro navigaci: odstranění dávno otevřených obrazovek («dům», «profil») by vedlo k neočekávanému chování.