LIFO Cache: essens, stackalgoritm och hur den fungerar

Vad är LIFO Cache?

LIFO Cache (Last In First Out Cache) — är en cache av begränsad storlek implementerad baserat på en stack. När ett nytt element läggs till i en full cache tas det senaste (översta) elementet bort och det nya elementet tar dess plats. Namnet «Last In First Out» betyder att elementet som kom in i cachen sist kommer att tas bort först.

En sådan policy skiljer sig radikalt från LRU och FIFO. Medan LRU försöker behålla de mest aktuella uppgifterna (baserat på senaste åtkomsttid) och FIFO bevarar dataåldern, offrar LIFO medvetet färska data. Detta kan verka ologiskt för cachning, men för vissa scenarier visar sig LIFO vara den optimala lösningen.

Den klassiska implementeringen av LIFO Cache använder en stack baserad på en array eller länkad lista. En array ger kompakt lagring och cachelokalitet, men kräver förutseende minnestilldelning för maxSize. En länkad lista är mer flexibel, men varje element kräver extra minne för pekare (8–16 byte per element).

Grundläggande operationer för LIFO Cache

Operationen push(value) lägger till ett element på stackens topp. Om storleken har nått maxSize tas toppen bort före insättning. Operationen pop() tar bort och returnerar det översta elementet — användbart för scenarier med «ångra senaste åtgärden». Operationen peek() returnerar det översta elementet utan borttagning — för att visa senast sparade tillstånd utan att ändra stacken.

Hur LIFO Cache fungerar

Funktionsprincipen för LIFO Cache är extremt enkel: alla operationer utförs på en ände av strukturen — stackens topp. När ett nytt element läggs till placeras det på toppen. Om stacken är full trycks det översta elementet ut (tas bort) och det nya elementet tar dess plats. Undanträngning påverkar alltid bara ett element — toppen — så algoritmen kräver ingen genomsökning eller sökning.

Denna egenskap gör LIFO Cache till den snabbaste bland alla undanträngningspolicyer: alla operationer utförs i O(1) utan några extra datastrukturer. Ingen hashtabell behövs för sökning, ingen dubbelt länkad lista behövs för omordning — en enkel pekare till stackens topp räcker. Minne förbrukas minimalt: endast för lagring av själva elementen.

Enkelheten har dock en baksida: LIFO Cache tar inte hänsyn till frekvensen eller tiden för senaste åtkomst till data. Om applikationen först begär data A, B, C och sedan igen A — vid överflöde kommer C (senast tillagd) att tas bort, även om A inte längre är aktuell. För scenarier med allmän cachning gör detta LIFO till det sämsta valet, eftersom färska data ofta är mest värdefulla.

Stackstorlek och minneshantering

För LIFO Cache baserad på array ställs storleken in vid skapandet och ändras inte dynamiskt. Om stacken är full och push inträffar — skrivs det översta elementet över. För implementering på länkad lista allokeras minne för varje element vid behov, men när gränsen nås kopplas den gamla noden bort och kan samlas in av skräpsamlaren. I mobila applikationer rekommenderas att använda en array för LIFO Cache, eftersom den inte skapar extra belastning på GC.

LIFO vs LRU och FIFO: jämförelse av strategier

Valet av undanträngningsstrategi påverkar direkt effektiviteten av cachning. LIFO, LRU och FIFO representerar olika angreppssätt på samma fråga: vilket element ska tas bort vid överflöde? Varje angreppssätt är optimalt för sin egen uppgiftsklass.

LRU ger vanligtvis bäst hit-ratio, men kräver mer minne och är mer komplext att implementera. FIFO — en kompromiss mellan prestanda och hit-ratio, användbart för strömmande data. LIFO — det enklaste, men med låg hit-ratio: bör endast tillämpas när semantiken «sist in – först ut» överensstämmer med affärslogiken (navigering, ångring av operationer).

Var används LIFO Cache

Trots begränsad lämplighet för allmän cachning finner LIFO Cache tillämpning i specifika scenarier där ordningen för databehandling är omvänd till ankomstordningen. Låt oss titta på de viktigaste fallen.

Navigeringsstackar

I mobila applikationer används en navigeringsstack: när en ny skärm öppnas placeras den på stackens topp, när knappen «Tillbaka» trycks — tas den bort. Om stackdjupet begränsas (till exempel max 10 skärmar) kommer LIFO Cache automatiskt att ta bort den senaste skärmen när gränsen överskrids. Detta möjliggör kontroll av minnesförbrukningen för navigeringsstacken utan att förlora tidigare öppnade skärmar.

Undo/Redo-stackar

Mekanismen för att ångra åtgärder (Undo) — ett klassiskt exempel på LIFO. Varje användaråtgärd sparas i en stack. När Undo anropas ångras den senaste åtgärden och flyttas till Redo-stacken. Begränsning av stackstorlekar via LIFO Cache garanterar att när gränsen överskrids förblir de äldsta åtgärderna (på stackens botten) och de nyaste kasseras — vilket är logiskt, eftersom användaren vanligtvis ångrar senaste åtgärder och gamla är inte längre aktuella.

Buffring av temporära beräkningar

Vid rekursiva beräkningar med återgång (backtracking) sparas resultaten av mellanliggande steg i LIFO-ordning. När bufferten svämmar över kasseras det senaste resultatet — detta är acceptabelt eftersom algoritmen kan räkna om det vid behov. Denna metod används i tolkprogram, kompilatorer och algoritmer för grafsökning med djupbegränsning.

Kodexempel för LIFO Cache

Låt oss titta på implementeringen av LIFO Cache i Kotlin med hjälp av en array med fast storlek. Arrayen ger bäst prestanda och minimal minnesförbrukning för mobila enheter.

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--  // kassera äldsta när 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]
    }
}

Indexet top pekar på stackens topp. push ökar top och skriver värdet; om arrayen är full (top == maxSize - 1) minskas top före skrivning — stackens topp skrivs över, vilket implementerar LIFO-undanträngning. Metoden pop returnerar elementet och minskar top, medan peek helt enkelt läser det översta elementet utan att ändra stacken.

Exempel: navigeringsstack med LIFO Cache

Låt oss titta på användningen av LIFO Cache för att begränsa navigeringsdjupet i Jetpack Compose. När en ny skärm öppnas läggs den till i stacken, och när gränsen överskrids trängs den senaste skärmen undan.

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

I detta exempel använder NavigationStack LIFO Cache för att lagra skärmhistorik. När navigateTo anropas läggs skärmen till i stacken, vid goBack — tas den sista bort. Om användaren har öppnat 11 skärmar med en gräns på 10 kommer den senaste (11:e) att tränga undan den föregående (10:e) — den första skärmen finns kvar i stacken, vilket motsvarar användarens förväntningar vid återkomst. Denna strategi är effektivare än LRU för navigering: borttagning av länge sedan öppnade skärmar («hemsida», «profil») skulle leda till oväntat beteende.