LIFO Cache: суть, алгоритм стеку та як працює

Що таке LIFO Cache?

LIFO Cache (Last In First Out Cache) — це кеш обмеженого розміру, реалізований на основі стеку. При додаванні нового елемента в заповнений кеш видаляється найсвіжіший (верхній) елемент, а новий займає його місце. Назва «Last In First Out» означає, що елемент, який потрапив у кеш останнім, буде видалений першим.

Така політика радикально відрізняється від LRU та FIFO. Якщо LRU намагається зберегти найбільш актуальні дані (за часом останнього звернення), а FIFO зберігає «вік» даних, то LIFO свідомо жертвує свіжими даними. Це може здатися нелогічним для кешування, але для певних сценаріїв LIFO виявляється оптимальним рішенням.

Класична реалізація LIFO Cache використовує стек на основі масиву або зв'язного списку. Масив забезпечує компактне зберігання та кеш-локальність, але вимагає попереднього виділення пам'яті під maxSize. Зв'язний список гнучкіший, але кожен елемент вимагає додаткової пам'яті на вказівники (8–16 байт на елемент).

Основні операції 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--  // 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]
    }
}

Індекс 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, для навігації: видалення давно відкритих екранів («домашній», «профіль») призвело б до неочікуваної поведінки.