LIFO Cache: mahiyyəti, stack alqoritmi və necə işləyir

LIFO Cache nədir?

LIFO Cache (Last In First Out Cache) — stack əsasında həyata keçirilmiş məhdud ölçülü keşdir. Dolu keşə yeni element əlavə edilərkən ən təzə (yuxarı) element silinir və yeni element onun yerini tutur. «Last In First Out» adı o deməkdir ki, keşə ən son daxil olan element ən əvvəl silinəcək.

Bu siyasət LRU və FIFO-dan köklə fərqlənir. LRU ən aktual məlumatları (son çağrış vaxtına görə) saxlamağa çalışarkən, FIFO məlumatların «yaşını» saxlayır, LIFO isə şürurlə təzə məlumatları qurban verir. Bu, keşləmə üçün məntıqsiz görünə bilər, lakin müəyyən ssenarilərdə LIFO optimal həll yolu olur.

Klassik LIFO Cache tətbiqi massiv və ya əlaqəli siyahı əsasında stackdan istifadə edir. Massiv yığcam saxlama və keş lokallığı təmin edir, lakin maxSize üçün əvvəlcədən yaddaş ayrılması tələb edir. Əlaqəli siyahı daha çevikdir, lakin hər element göstəricilər üçün əlavə yaddaş tələb edir (element başına 8–16 bayt).

LIFO Cache-in əsas əməliyyatları

push(value) əməliyyatı elementi stackın yuxarısına əlavə edir. Ɔlçü maxSize-a çatıbsa, daxil etməzdən əvvəl yuxarı hissə silinir. pop() əməliyyatı yuxarı elementi silir və qaytarır — «son əməliyyatı geri qaytarma» ssenariləri üçün faydalıdır. peek() əməliyyatı yuxarı elementi silmədən qaytarır — stackı dəyişmədən son saxlanmış vəziyyətə baxmaq üçün.

LIFO Cache necə işləyir

LIFO Cache-in işləmə prinsipi olduqca sadədir: bütün əməliyyatlar strukturun bir ucunda — stackın yuxarısında yerinə yetirilir. Yeni element əlavə edilərkən o, yuxarıya qoyulur. Stack doludursa, yuxarı element itələnir (silinir), yeni element isə onun yerini tutur. Sıxışdırma həmişə yalnız bir elementə — yuxarıya təsir edir, buna görə alqoritm axtarış və ya sıralama tələb etmir.

Bu xüsusiyyət LIFO Cache-i bütün sıxışdırma siyasətləri arasında ən sürətli edir: bütün əməliyyatlar heç bir əlavə məlumat strukturu olmadan O(1) vaxtında yerinə yetirilir. Axtarış üçün hash cədvəli, yenidən düzəltmə üçün iki tərəfli siyahı lazım deyil — sadəcə stackın yuxarısına göstərici kifayətdir. Yaddaş minimal sərfolunur: yalnız elementlərin özlərini saxlamaq üçün.

Lakin sadəliyin əks tərəfi də var: LIFO Cache məlumatlara müraciət tezliyini və ya son çağrış vaxtını nəzərə almır. Proqram əvvəlcə A, B, C məlumatlarını, sonra yenə A-nı tələb edərsə — daşma zamanı C (son əlavə edilmiş) silinəcək, hətta A artıq aktual olmasa belə. Ümumi keşləmə ssenariləri üçün bu, LIFO-nu ən pis seçim edir, çünki təzə məlumatlar çox vaxt ən dəyərlidir.

Stack ölçüsü və yaddaş idarəçiliyi

Massiv əsaslı LIFO Cache üçün ölçü yaradılma zamanı təyin edilir və dinamik dəyişmir. Stack doludursa və push baş verərsə — yuxarı element üstə yazılır. Əlaqəli siyahı tətbiqində hər element üçün yaddaş ehtiyac olduqca ayrılır, lakin limit çatıldıqda köhnə düün ayrılır və zibil yığıcı tərəfindən toplana bilər. Mobil proqramlarda LIFO Cache üçün massivdən istifadə etmək tövsiyə olunur, çünki o, GC-ə əlavə yük yaratmır.

LIFO vs LRU və FIFO: strategiyaların müqayisəsi

Sıxışdırma strategiyasının seçimi keşləmənin səmərəliliyinə birbaşa təsir edir. LIFO, LRU və FIFO bir suala müxtəlif yanaşmaları təmsil edir: daşma zamanı hansı elementi silməli? Hər yanaşma öz tapşırıq sinfi üçün optimaldır.

LRU adətən ən yaxşı hit-ratio verir, lakin daha çox yaddaş və mürəkkəb tətbiq tələb edir. FIFO — performans və hit-ratio arasında kompromisdir, axın məlumatları üçün faydalıdır. LIFO — ən sadə, lakin aşağı hit-ratio ilə: onu yalnız «son gələn — birinci çıxan» semantikası biznes məntiqinə uyğun olduqda tətbiq etmək lazımdır (naviqasiya, əməliyyatları geri qaytarma).

LIFO Cache harada tətbiq olunur

Ümumi keşləmə üçün məhdud yararlılığına baxmayaraq, LIFO Cache məlumat emalı sırasının qəbul sırasına tərs olduğu konkret ssenarilərdə tətbiq tapır. Əsas halları nəzərdən keçirək.

Naviqasiya stackləri

Mobil proqramlarda naviqasiya stacki istifadə olunur: yeni ekran açıldıqda stackın yuxarısına yerləşdirilir, «Geri» düyməsi basıldıqda çıxarılır. Stackin dərinliyi məhdudlaşdırılarsa (məsələn, maksimum 10 ekran), LIFO Cache limiti aşdıqda avtomatik olaraq ən son ekranı siləcək. Bu, əvvəl açılmış ekranları itirmədən naviqasiya stackinin yaddaş istehlakını idarə etməyə imkan verir.

Undo/Redo stackləri

Əməliyyatları geri qaytarma mexanizmi (Undo) — LIFO-nun klassik nümunəsidir. İstifadəçinin hər bir əməliyyatı stackdə saxlanılır. Undo çağrıldıqda son əməliyyat geri qaytarılır və Redo stackinə köçürülür. LIFO Cache vasitəsilə stack ölçülərinin məhdudlaşdırılması limiti aşdıqda ən köhnə əməliyyatların (stackin dibində) qalmasını, ən yenilərin isə atılmasını təmin edir — bu məntiqlidir, çünki istifadəçi adətən son əməliyyatları geri qaytarır, köhnələr isə artıq aktual deyil.

Müvəqqəti hesablamaların buferləşməsi

Geri qayıtma (backtracking) ilə rekursiv hesablamalarda aralıq addımların nəticələri LIFO sırası ilə saxlanılır. Bufer daşdıqda son nəticə atılır — bu məqbuldur, çünki alqoritm lazım olduqda onu yenidən hesablaya bilər. Bu yanaşma parserlərdə, kompilyatorlarda və dərinlik məhdudiyyəti olan qrafik keçid alqoritmlərində istifadə olunur.

LIFO Cache kod nümunələri

Sabit ölçülü massivdən istifadə edərək Kotlin-də LIFO Cache tətbiqini nəzərdən keçirək. Massiv mobil cihazlar üçün ən yaxşı performans və minimal yaddaş istehlakı təmin edir.

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--  // dolu olanda ən köhnəni sil
        }
        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 indeksi stackın yuxarısını göstərir. push top-u artırır və dəyəri yazır; massiv doludursa (top == maxSize - 1), yazıdan əvvəl top azaldılır — stackın yuxarısı üstə yazılır, bu da LIFO sıxışdırmasını həyata keçirir. pop metodu elementi qaytarır və top-u azaldır, peek isə stackı dəyişmədən yuxarı elementi oxuyur.

Nümunə: LIFO Cache ilə naviqasiya stacki

Jetpack Compose-da naviqasiya dərinliyini məhdudlaşdırmaq üçün LIFO Cache istifadəsini nəzərdən keçirək. Yeni ekran açıldıqda stackə əlavə edilir, limit aşıldıqda isə ən son ekran sıxışdırılır.

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

Bu nümunədə NavigationStack ekran tarixçəsini saxlamaq üçün LIFO Cache istifadə edir. navigateTo çağrıldıqda ekran stackə əlavə edilir, goBack zamanı isə sonuncu silinir. İstifadəçi limit 10 olduğu halda 11 ekran açarsa, ən sonuncu (11-ci) əvvəlki (10-cu) ekranı sıxışdırır — ilk ekran stackdə qalır, bu da geri qayıdarkən istifadəçinin gözləntilərinə uyğundur. Bu strategiya naviqasiya üçün LRU-dan daha səmərəlidir: çoxdan açılmış ekranların («anasəhifə», «profil») silinməsi gözlənilən davranışa səbəb olardı.