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