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 — горњи елеменат се преписује. За имплементацију на повезаној листи, меморија се алоцира за сваки елеменат по потреби, али након достизања лимита, стари чвор се одваја и може да га сакупи garbage collector. У мобилним апликацијама препоручује се кориштење низа за 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 за навигацију: уклањање давно отворених екрана («почетна», «профил») довело би до неочекиваног понашања.