LIFO Cache: ουσία, αλγόριθμος στοίβας και πώς λειτουργεί

Τι είναι το LIFO Cache;

LIFO Cache (Last In First Out Cache) — είναι μια μνήμη cache περιορισμένου μεγέθους, που υλοποιείται με βάση τη στοίβα. Κατά την προσθήκη ενός νέου στοιχείου σε μια πλήρη cache, το πιο πρόσφατο (κατώτατο) στοιχείο αφαιρείται και το νέο στοιχείο παίρνει τη θέση του. Το όνομα "Last In First Out" σημαίνει ότι το στοιχείο που εισήλθε τελευταίο στην cache θα αφαιρεθεί πρώτο.

Αυτή η πολιτική διαφέρει ριζικά από το LRU και το FIFO. Ενώ το LRU προσπαθεί να διατηρήσει τα πιο επίκαιρα δεδομένα (με βάση τον χρόνο τελευταίας πρόσβασης) και το FIFO διατηρεί την "ηλικία" των δεδομένων, το LIFO θυσιάζει συνειδητά τα φρέσκα δεδομένα. Αυτό μπορεί να φαίνεται απαράσκευαστο για την προσωρινή αποθήκευση, αλλά για ορισμένα σενάρια το LIFO αποδεικνύεται η βέλτιστη λύση.

Η κλασική υλοποίηση LIFO Cache χρησιμοποιεί στοίβα βασισμένη σε πίνακα ή συνδεδεμένη λίστα. Ο πίνακας παρέχει συμπαγή αποθήκευση και τοπικότητα cache, αλλά απαιτεί προηγούμενη εκχώρηση μνήμης για maxSize. Η συνδεδεμένη λίστα είναι πιο ευέλικτη, αλλά κάθε στοιχείο απαιτεί επιπλέον μνήμη για δείκτες (8–16 byte ανά στοιχείο).

Βασικές λειτουργίες LIFO Cache

Η λειτουργία push(value) προσθέτει ένα στοιχείο στην κορυφή της στοίβας. Αν το μέγεθος έχει φτάσει maxSize, πριν την εισαγωγή η κορυφή αφαιρείται. Η λειτουργία pop() αφαιρεί και επιστρέφει το κατώτατο στοιχείο — χρήσιμη για σενάρια "αναίρεσης της τελευταίας ενέργειας". Η λειτουργία peek() επιστρέφει το κατώτατο στοιχείο χωρίς αφαίρεση — για προβολή της τελευταίας αποθηκευμένης κατάστασης χωρίς να αλλάξει τη στοίβα.

Πώς λειτουργεί το LIFO Cache

Η αρχή λειτουργίας του LIFO Cache είναι εξαιρετικά απλή: όλες οι λειτουργίες εκτελούνται σε ένα άκρο της δομής — την κορυφή της στοίβας. Κατά την προσθήκη ενός νέου στοιχείου, αυτό τοποθετείται στην κορυφή. Εάν η στοίβα είναι γεμάτη, το κατώτατο στοιχείο αποβάλλεται (αφαιρείται) και το νέο παίρνει τη θέση του. Η αποβολή επηρεάζει πάντα μόνο ένα στοιχείο — την κορυφή, επομένως ο αλγόριθμος δεν απαιτεί αναζήτηση ή αναζήτηση.

Αυτή η ιδιότητα κάνει το LIFO Cache το πιο γρήγορο μεταξύ όλων των πολιτικών αποβολής: όλες οι λειτουργίες εκτελούνται σε O(1) χωρίς καμία επιπλέον δομή δεδομένων. Δεν χρειάζεται πίνακας κατατεταγμένων για αναζήτηση, δεν χρειάζεται διπλά συνδεδεμένη λίστα για αναδιάταξη — ένας απλός δείκτης στην κορυφή της στοίβας είναι αρκετός. Η μνήμη καταναλώνεται ελάχιστα: μόνο για την αποθήκευση αυτών των στοιχείων.

Ωστόσο, η απλότητα έχει και αρνητική πλευρά: το LIFO Cache δεν λαμβάνει υπόψη τη συχνότητα ή τον χρόνο τελευταίας πρόσβασης στα δεδομένα. Εάν η εφαρμογή ζητά πρώτα δεδομένα A, B, C και στη συνέχεια ξανά A — κατά την υπερχείλιση θα αφαιρεθεί το C (το τελευταίο προστιθένο), ακόμη και αν το A δεν είναι πλέον επίκαιρο. Για σενάρια γενικής προσωρινής αποθήκευσης αυτό κάνει το LIFO τη χειρότερη επιλογή, καθώς τα φρέσκα δεδομένα είναι συχνά τα πιο πολύτιμα.

Μέγεθος στοίβας και διαχείριση μνήμης

Για LIFO Cache βασισμένο σε πίνακα, το μέγεθος καθορίζεται κατά τη δημιουργία και δεν αλλάζει δυναμικά. Εάν η στοίβα είναι γεμάτη και συμβεί push — το κατώτατο στοιχείο αντικαθίσταται. Για υλοποίηση σε συνδεδεμένη λίστα, η μνήμη εκχωρείται για κάθε στοιχείο κατά τη ζήτηση, αλλά μετά την επίτευξη του ορίου, ο παλιός κόμβος αποσυνδέεται και μπορεί να συλλεχθεί από τον συλλέκτη σκουπιδιών. Σε εφαρμογές κινητών συνιστάται η χρήση πίνακα για LIFO Cache, καθώς δεν δημιουργεί επιπλέον φορτίο στον GC.

LIFO vs LRU και FIFO: σύγκριση στρατηγικών

Η επιλογή στρατηγικής αποβολής επηρεάζει άμεσα την αποτελεσματικότητα της προσωρινής αποθήκευσης. Το LIFO, LRU και FIFO αντιπροσωπεύουν διαφορετικές προσεγγίσεις στην ίδια ερώτηση: ποιο στοιχείο να αφαιρέσουμε κατά την υπερχείλιση; Κάθε προσέγγιση είναι βέλτιστη για τη δική της κλάση εργασιών.

LRU συνήθως δίνει το καλύτερο hit-ratio, αλλά απαιτεί περισσότερη μνήμη και είναι πιο περίπλοκη στην υλοποίηση. FIFO — συμβιβασμός μεταξύ απόδοσης και hit-ratio, χρήσιμο για ρέοντα δεδομένα. LIFO — το απλούστερο, αλλά με χαμηλό hit-ratio: πρέπει να εφαρμόζεται μόνο όταν η σημασία "τελευταίο εισέρχεται – πρώτο εξέρχεται" ταιριάζει με την επιχειρηματική λογική (πλοήγηση, αναίρεση λειτουργιών).

Που εφαρμόζεται το LIFO Cache

Παρά την περιορισμένη καταλληλότητα για γενική προσωρινή αποθήκευση, το LIFO Cache βρίσκει εφαρμογή σε συγκεκριμένα σενάρια όπου η σειρά επεξεργασίας δεδομένων είναι αντίστροφη της σειράς άφιξης. Ας δούμε τις κύριες περιπτώσεις.

Στοίβες πλοήγησης

Σε εφαρμογές κινητών χρησιμοποιείται στοίβα πλοήγησης: κατά το άνοιγμα μιας νέας οθόνης, αυτή τοποθετείται στην κορυφή της στοίβας, με το πάτημα του κουμπιού "Πίσω" — αφαιρείται. Εάν το βάθος της στοίβας είναι περιορισμένο (για παράδειγμα, μέχρι 10 οθόνες), το LIFO Cache θα αφαιρεί αυτόματα την πιο πρόσφατη οθόνη κατά την υπέρβαση του ορίου. Αυτό επιτρέπει τον έλεγχο της κατανάλωσης μνήμης της στοίβας πλοήγησης χωρίς απώλεια των προηγούμενα ανοιγμένων οθονών.

Στοίβες Undo/Redo

Ο μηχανισμός αναίρεσης ενεργειών (Undo) — κλασικό παράδειγμα LIFO. Κάθε ενέργεια χρήστη αποθηκεύεται σε μια στοίβα. Κατά την κλήση Undo, η τελευταία ενέργεια αναιρείται και μεταφέρεται στη στοίβα Redo. Ο περιορισμός του μεγέθους των στοιβών μέσω LIFO Cache εγγυάται ότι κατά την υπέρβαση του ορίου, οι παλαιότερες ενέργειες (στον πυθμένα της στοίβας) παραμένουν και οι νεότερες απορρίπτονται — που είναι λογικό, καθώς ο χρήστης συνήθως αναιρεί πρόσφατες ενέργειες και οι παλιές δεν είναι πλέον επίκαιρες.

Ρυθμιστική προσωρινών υπολογισμών

Σε αναδρομικούς υπολογισμούς με επαναφορά (backtracking), τα αποτελέσματα των ενδιάμεσων βημάτων αποθηκεύονται σε σειρά LIFO. Όταν η ρυθμιστική υπερχειλίσει, το τελευταίο αποτέλεσμα απορρίπτεται — αυτό είναι αποδεκτό, καθώς ο αλγόριθμος μπορεί να το επανυπολογίσει αν χρειαστεί. Αυτή η προσέγγιση χρησιμοποιείται σε αναλυτές, μεταγλωττιστές και αλγόριθμους διάσχισης γράφων με περιορισμό βάθους.

Παραδείγματα κώδικα LIFO Cache

Ας εξετάσουμε την υλοποίηση LIFO Cache σε Kotlin με χρήση πίνακα σταθερού μεγέθους. Ο πίνακας παρέχει την καλύτερη απόδοση και ελάχιστη κατανάλωση μνήμης για κινητές συσκευές.

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--  // απόρριψη του παλαιότερου όταν είναι γεμάτο
        }
        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]
    }
}

Ο δείκτης top δείχνει στην κορυφή της στοίβας. Το push αυξάνει το top και γράφει την τιμή; εάν ο πίνακας είναι γεμάτος (top == maxSize - 1), πριν την εγγραφή το top μειώνεται — η κορυφή της στοίβας αντικαθίσταται, που υλοποιεί την αποβολή LIFO. Η μέθοδος pop επιστρέφει το στοιχείο και μειώνει το top, ενώ το peek απλώς διαβάζει το κατώτατο στοιχείο χωρίς να αλλάζει τη στοίβα.

Παράδειγμα: στοίβα πλοήγησης με LIFO Cache

Ας εξετάσουμε τη χρήση LIFO Cache για τον περιορισμό του βάθους πλοήγησης στο Jetpack Compose. Κατά το άνοιγμα μιας νέας οθόνης, αυτή προστίθεται στη στοίβα, και κατά την υπέρβαση του ορίου, η πιο πρόσφατη οθόνη αποβάλλεται.

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

Σε αυτό το παράδειγμα, το NavigationStack χρησιμοποιεί LIFO Cache για την αποθήκευση του ιστορικού οθονών. Κατά την κλήση navigateTo, η οθόνη προστίθεται στη στοίβα, κατά goBack — η τελευταία αφαιρείται. Εάν ο χρήστης έχει ανοίξει 11 οθόνες με όριο 10, η πιο πρόσφατη (11η) θα αποβάλει την προηγούμενη (10η) — η πρώτη οθόνη παραμένει στη στοίβα, που ανταποκρίνεται στις προσδοκίες του χρήστη κατά την επιστροφή. Αυτή η στρατηγική είναι πιο αποτελεσματική από το LRU για πλοήγηση: η αφαίρεση οθονών που ανοίχτηκαν προ καιρού ("αρχική", "προφίλ") θα οδηγούσε σε απροσδόκητη συμπεριφορά.