LIFO Cache: essenza, algoritmo dello stack e come funziona

Cos'è LIFO Cache?

LIFO Cache (Last In First Out Cache) è una cache di dimensione fissa implementata su uno stack. Quando un nuovo elemento viene aggiunto a una cache piena, l'elemento più recente (cima) viene rimosso e il nuovo elemento prende il suo posto. Il nome “Last In First Out” significa che l'elemento entrato per ultimo nella cache verrà espulso per primo.

Questa politica differisce radicalmente da LRU e FIFO. Mentre LRU cerca di mantenere i dati più rilevanti (per tempo dell'ultimo accesso) e FIFO preserva l'“età” dei dati, LIFO sacrifica deliberatamente i dati recenti. Questo può sembrare controintuitivo per il caching, ma per certi scenari LIFO si rivela la soluzione ottimale.

Un'implementazione classica di LIFO Cache utilizza uno stack basato su array o lista concatenata. Un array fornisce archiviazione compatta e località della cache, ma richiede pre-allocazione di memoria per maxSize. Una lista concatenata è più flessibile, ma ogni elemento richiede memoria aggiuntiva per i puntatori (8–16 byte per elemento).

Operazioni Base di LIFO Cache

L'operazione push(value) aggiunge un elemento sulla cima dello stack. Se la dimensione raggiunge maxSize, la cima viene rimossa prima dell'inserimento. L'operazione pop() rimuove e restituisce l'elemento superiore — utile per scenari di “annullamento dell'ultima azione”. L'operazione peek() restituisce l'elemento superiore senza rimuoverlo — per visualizzare l'ultimo stato salvato senza modificare lo stack.

Come funziona LIFO Cache

Il principio di funzionamento di LIFO Cache è estremamente semplice: tutte le operazioni vengono eseguite su un'estremità della struttura — la cima dello stack. Quando un nuovo elemento viene aggiunto, viene posizionato in cima. Se lo stack è pieno, l'elemento in cima viene rimosso e il nuovo prende il suo posto. L'espulsione colpisce sempre un solo elemento — la cima — quindi l'algoritmo non richiede iterazione o ricerca.

Questa proprietà rende LIFO Cache il più veloce tra tutte le politiche di espulsione: tutte le operazioni vengono eseguite in O(1) senza strutture dati aggiuntive. Nessuna tabella hash per ricerche, nessuna lista doppiamente concatenata per riordinamento — solo un semplice puntatore alla cima dello stack. Il consumo di memoria è minimo: solo l'archiviazione degli elementi stessi.

Tuttavia, la semplicità ha un rovescio della medaglia: LIFO Cache non considera la frequenza o il tempo dell'ultimo accesso ai dati. Se un'applicazione richiede prima i dati A, B, C e poi di nuovo A, C (l'ultimo aggiunto) verrà espulso quando la cache è piena, anche se A non è più rilevante. Per scenari di caching generale questo rende LIFO la scelta peggiore, poiché i dati recenti sono spesso i più preziosi.

Dimensione dello Stack e Gestione della Memoria

Per un LIFO Cache basato su array, la dimensione viene impostata alla creazione e non cambia dinamicamente. Se lo stack è pieno e si verifica un push, l'elemento in cima viene sovrascritto. Per un'implementazione con lista concatenata, la memoria viene allocata per elemento secondo necessità, ma quando viene raggiunto il limite, il vecchio nodo viene scollegato e può essere raccolto dal garbage collector. Nelle applicazioni mobili si consiglia di utilizzare un array per LIFO Cache, poiché non crea carico aggiuntivo sul GC.

LIFO vs LRU e FIFO: Confronto delle Strategie

La scelta della strategia di espulsione influisce direttamente sull'efficienza del caching. LIFO, LRU e FIFO rappresentano approcci diversi alla stessa domanda: quale elemento rimuovere quando la cache è piena. Ogni approccio è ottimale per la propria classe di compiti.

LRU offre tipicamente il miglior tasso di hit ma richiede più memoria ed è più complesso da implementare. FIFO è un compromesso tra prestazioni e tasso di hit, utile per dati in streaming. LIFO è il più semplice ma con un basso tasso di hit: dovrebbe essere usato solo quando la semantica “ultimo entrato, primo uscito” corrisponde alla logica di business (navigazione, operazioni di annullamento).

Dove viene usato LIFO Cache

Nonostante la sua idoneità limitata per il caching generale, LIFO Cache trova impiego in scenari specifici dove l'ordine di elaborazione dei dati è inverso all'ordine di arrivo. Consideriamo i casi principali.

Stack di Navigazione

Nelle applicazioni mobili, viene utilizzato uno stack di navigazione: quando viene aperta una nuova schermata, viene posizionata sulla cima dello stack; quando viene premuto il pulsante “Indietro”, viene rimossa. Se la profondità dello stack è limitata (ad esempio, massimo 10 schermate), LIFO Cache espellerà automaticamente la schermata più recente quando il limite viene superato. Ciò consente di controllare il consumo di memoria dello stack di navigazione senza perdere le schermate aperte in precedenza.

Stack Annulla/Ripeti

Il meccanismo di annullamento (Undo) è un classico esempio di LIFO. Ogni azione dell'utente viene salvata in uno stack. Quando viene chiamato Undo, l'ultima azione viene annullata e spostata nello stack Ripeti. La limitazione della dimensione degli stack tramite LIFO Cache garantisce che quando il limite viene superato, le azioni più vecchie (in fondo allo stack) rimangano mentre quelle più recenti vengano scartate — il che è logico poiché l'utente di solito annulla azioni recenti mentre quelle vecchie non sono più rilevanti.

Buffer di Calcoli Temporanei

Nei calcoli ricorsivi con backtracking, i risultati dei passaggi intermedi vengono salvati in ordine LIFO. Quando il buffer trabocca, l'ultimo risultato viene scartato — questo è accettabile perché l'algoritmo può ricalcolarlo se necessario. Questo approccio viene utilizzato in parser, compilatori e algoritmi di attraversamento di grafi con limiti di profondità.

Esempi di Codice LIFO Cache

Esaminiamo un'implementazione di LIFO Cache in Kotlin utilizzando un array di dimensione fissa. Un array offre le migliori prestazioni e il minimo consumo di memoria per dispositivi mobili.

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--  // discard oldest when 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]
    }
}

L'indice top punta alla cima dello stack. push incrementa top e scrive il valore; se l'array è pieno (top == maxSize - 1), top viene decrementato prima della scrittura — la cima dello stack viene sovrascritta, implementando l'espulsione LIFO. Il metodo pop restituisce l'elemento e decrementa top, mentre peek legge semplicemente l'elemento superiore senza modificare lo stack.

Esempio: Stack di Navigazione con LIFO Cache

Considera l'uso di LIFO Cache per limitare la profondità di navigazione in Jetpack Compose. Quando viene aperta una nuova schermata, viene aggiunta allo stack e quando il limite viene superato, la schermata più recente viene espulsa.

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

In questo esempio, NavigationStack utilizza LIFO Cache per memorizzare la cronologia delle schermate. Quando viene chiamato navigateTo, la schermata viene aggiunta allo stack; quando viene chiamato goBack, l'ultima viene rimossa. Se l'utente ha aperto 11 schermate con un limite di 10, la più recente (11ª) espellerà la precedente (10ª) — la prima schermata rimane nello stack, corrispondendo alle aspettative dell'utente durante la navigazione indietro. Questa strategia è più efficiente di LRU per la navigazione: rimuovere schermate aperte da molto tempo (“home”, “profilo”) porterebbe a un comportamento imprevisto.