LIFO Cache: özü, yığın algoritması ve nasıl çalışır

LIFO Cache Nedir?

LIFO Cache (Last In First Out Cache), bir yığın üzerinde uygulanan sabit boyutlu bir önbellektir. Dolu bir önbelleğe yeni bir öğe eklendiğinde, en yeni (tepe) öğe kaldırılır ve yeni öğe onun yerini alır. “Last In First Out” adı, önbelleğe en son giren öğenin ilk çıkarılacağı anlamına gelir.

Bu politika, LRU ve FIFO'dan kökten farklıdır. LRU en alakalı verileri (son erişim zamanına göre) tutmaya çalışırken ve FIFO verilerin “yaşını” korurken, LIFO bilinçli olarak yeni verileri feda eder. Bu, önbelleğe alma için sezgilere aykırı görünebilir, ancak belirli senaryolar için LIFO en uygun çözüm olduğunu kanıtlar.

Klasik bir LIFO Cache uygulaması, bir dizi veya bağlantılı listeye dayalı bir yığın kullanır. Bir dizi, kompakt depolama ve önbellek yerelliği sağlar ancak maxSize için önceden bellek ayırmayı gerektirir. Bağlantılı liste daha esnektir, ancak her öğe işaretçiler için ek bellek gerektirir (öğe başına 8–16 bayt).

LIFO Cache Temel İşlemleri

push(value) işlemi, yığının tepesine bir öğe ekler. Boyut maxSize'a ulaşırsa, eklemeden önce tepe kaldırılır. pop() işlemi, üst öğeyi kaldırır ve döndürür — “son işlemi geri al” senaryoları için kullanışlıdır. peek() işlemi, üst öğeyi kaldırmadan döndürür — yığını değiştirmeden son kaydedilen durumu görüntülemek için.

LIFO Cache Nasıl Çalışır

LIFO Cache'in çalışma prensibi son derece basittir: tüm işlemler yapının bir ucunda — yığının tepesinde gerçekleştirilir. Yeni bir öğe eklendiğinde, tepeye yerleştirilir. Yığın doluysa, tepe öğesi çıkarılır (kaldırılır) ve yenisi onun yerini alır. Çıkarma her zaman yalnızca bir öğeyi — tepeyi — etkiler, bu nedenle algoritma yineleme veya arama gerektirmez.

Bu özellik, LIFO Cache'i tüm çıkarma politikaları arasında en hızlısı yapar: tüm işlemler, ek veri yapıları olmadan O(1)'de çalışır. Aramalar için karma tablosu, yeniden sıralama için çift bağlantılı liste gerekmez — yalnızca yığının tepesine basit bir işaretçi yeterlidir. Bellek tüketimi minimumdur: yalnızca öğelerin kendilerinin depolanması.

Ancak, basitliğin bir dezavantajı vardır: LIFO Cache, verilerin sıklığını veya son erişim zamanını dikkate almaz. Bir uygulama önce A, B, C verilerini ve sonra tekrar A'yı talep ederse, önbellek dolduğunda C (son eklenen) çıkarılacaktır, A artık alakalı olmasa bile. Genel önbelleğe alma senaryoları için bu, LIFO'yu en kötü seçim haline getirir, çünkü yeni veriler genellikle en değerli olanlardır.

Yığın Boyutu ve Bellek Yönetimi

Dizi tabanlı bir LIFO Cache için boyut, oluşturma sırasında belirlenir ve dinamik olarak değişmez. Yığın doluysa ve push gerçekleşirse, tepe öğesi üzerine yazılır. Bağlantılı liste uygulaması için, bellek gerektiğinde öğe başına ayrılır, ancak sınıra ulaşıldığında eski düğüm ayrılır ve çöp toplayıcı tarafından toplanabilir. Mobil uygulamalarda, LIFO Cache için dizi kullanılması önerilir, çünkü GC üzerinde ek yük oluşturmaz.

LIFO vs LRU ve FIFO: Strateji Karşılaştırması

Çıkarma stratejisi seçimi, önbelleğe alma verimliliğini doğrudan etkiler. LIFO, LRU ve FIFO, aynı soruya farklı yaklaşımları temsil eder: önbellek dolduğunda hangi öğe kaldırılmalı? Her yaklaşım, kendi görev sınıfı için optimaldir.

LRU tipik olarak en iyi isabet oranını sağlar ancak daha fazla bellek gerektirir ve uygulaması daha karmaşıktır. FIFO, performans ve isabet oranı arasında bir uzlaşmadır, akış verileri için kullanışlıdır. LIFO en basitidir ancak düşük isabet oranına sahiptir: yalnızca “son giren ilk çıkar” anlamının iş mantığıyla (navigasyon, geri alma işlemleri) eşleştiği durumlarda kullanılmalıdır.

LIFO Cache Nerelerde Kullanılır

Genel önbelleğe alma için sınırlı uygunluğuna rağmen, LIFO Cache, veri işleme sırasının geliş sırasının tersi olduğu belirli senaryolarda kullanım alanı bulur. Ana durumları inceleyelim.

Navigasyon Yığınları

Mobil uygulamalarda bir navigasyon yığını kullanılır: yeni bir ekran açıldığında yığının tepesine yerleştirilir; “Geri” düğmesine basıldığında kaldırılır. Yığın derinliği sınırlıysa (örneğin, maksimum 10 ekran), LIFO Cache sınır aşıldığında otomatik olarak en yeni ekranı çıkarır. Bu, daha önce açılmış ekranları kaybetmeden navigasyon yığınının bellek tüketimini kontrol etmenizi sağlar.

Geri Al/Yinele Yığınları

Geri alma mekanizması (Undo), LIFO'nun klasik bir örneğidir. Her kullanıcı eylemi bir yığında kaydedilir. Undo çağrıldığında, son eylem geri alınır ve Yinele yığınına taşınır. LIFO Cache aracılığıyla yığın boyutunun sınırlandırılması, sınır aşıldığında en eski eylemlerin (yığının dibinde) kalmasını ve en yeni eylemlerin atılmasını sağlar — bu mantıklıdır çünkü kullanıcı genellikle yeni eylemleri geri alırken eskileri artık alakalı değildir.

Geçici Hesaplama Tamponlama

Geri izleme (backtracking) içeren özyinelemeli hesaplamalarda, ara adımların sonuçları LIFO sırasıyla kaydedilir. Tampon taştığında, son sonuç atılır — bu kabul edilebilir çünkü algoritma gerekirse yeniden hesaplayabilir. Bu yaklaşım ayrıştırıcılarda, derleyicilerde ve derinlik sınırı olan grafik geçiş algoritmalarında kullanılır.

LIFO Cache Kod Örnekleri

Sabit boyutlu bir dizi kullanarak Kotlin'de LIFO Cache uygulamasını inceleyelim. Bir dizi, mobil cihazlar için en iyi performansı ve minimum bellek tüketimini sağlar.

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 indeksi yığının tepesini gösterir. push, top'u artırır ve değeri yazar; dizi doluysa (top == maxSize - 1), yazmadan önce top azaltılır — yığının tepesi üzerine yazılır, bu da LIFO çıkarmayı uygular. pop yöntemi öğeyi döndürür ve top'u azaltır, peek ise yığını değiştirmeden üst öğeyi okur.

Örnek: LIFO Cache ile Navigasyon Yığını

Jetpack Compose'da navigasyon derinliğini sınırlamak için LIFO Cache kullanımını düşünün. Yeni bir ekran açıldığında yığına eklenir ve sınır aşıldığında en yeni ekran çıkarı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 örnekte, NavigationStack ekran geçmişini depolamak için LIFO Cache kullanır. navigateTo çağrıldığında ekran yığına eklenir; goBack çağrıldığında son ekran kaldırılır. Kullanıcı 10 limitiyle 11 ekran açtıysa, en yeni (11.) öncekini (10.) çıkaracaktır — ilk ekran yığında kalır, bu da geriye doğru gezinirken kullanıcının beklentileriyle eşleşir. Bu strateji, navigasyon için LRU'dan daha verimlidir: uzun süre önce açılmış ekranların (“ana sayfa”, “profil”) kaldırılması beklenmeyen davranışlara yol açacaktır.