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の動作原理は非常にシンプルです。すべての操作は構造体の一端 — スタックのトップで実行されます。新しい要素が追加されると、それがトップに配置されます。スタックが満杯の場合、トップ要素がポップ（削除）され、新しい要素がその場所を占めます。追い出しは常に1つの要素（トップ）のみに影響するため、アルゴリズムは反復や検索を必要としません。

この特性により、LIFO Cacheはすべての追い出しポリシーの中で最速になります。すべての操作は追加のデータ構造なしでO(1)で実行されます。検索用のハッシュテーブルも、並べ替え用の二重リンクリストも不要です — スタックのトップへの単純なポインタだけで十分です。メモリ消費は最小限で、要素自体のストレージのみです。

ただし、単純さには欠点があります。LIFO Cacheはデータの頻度や最終アクセス時間を考慮しません。アプリケーションが最初にデータA、B、Cを要求し、次に再びAを要求した場合、キャッシュが満杯になるとC（最後に追加されたもの）が追い出されます。たとえAがもはや関連性がなくてもです。一般的なキャッシュシナリオでは、これによりLIFOは最悪の選択となります。新しいデータが最も価値があることが多いからです。

スタックサイズとメモリ管理

配列ベースのLIFO Cacheの場合、サイズは作成時に設定され、動的には変更されません。スタックが満杯でpushが発生すると、トップ要素が上書きされます。リンクリスト実装の場合、必要に応じて要素ごとにメモリが割り当てられますが、制限に達すると古いノードが切り離され、ガベージコレクタによって収集されます。モバイルアプリケーションでは、GCに追加の負荷をかけないため、LIFO Cacheに配列を使用することをお勧めします。

LIFO vs LRUとFIFO：戦略の比較

追い出し戦略の選択はキャッシュ効率に直接影響します。LIFO、LRU、FIFOは同じ質問に対して異なるアプローチを表しています。キャッシュが満杯になったときにどの要素を削除するか。各アプローチは独自のタスククラスに対して最適です。

LRUは通常、最良のヒット率を提供しますが、より多くのメモリを必要とし、実装がより複雑です。FIFOはパフォーマンスとヒット率の妥協点であり、ストリーミングデータに役立ちます。LIFOは最もシンプルですが、ヒット率が低くなります。「最後に入ったものが最初に出る」というセマンティクスがビジネスロジック（ナビゲーション、元に戻す操作）と一致する場合にのみ使用する必要があります。

LIFO Cacheの使用例

一般的なキャッシュへの適合性は限られていますが、LIFO Cacheはデータ処理の順序が到着順序と逆になる特定のシナリオで使用されています。主なケースを見てみましょう。

ナビゲーションスタック

モバイルアプリケーションでは、ナビゲーションスタックが使用されます。新しい画面が開かれると、スタックのトップに配置されます。「戻る」ボタンが押されると、削除されます。スタックの深さが制限されている場合（たとえば最大10画面）、LIFO Cacheは制限を超えると自動的に最新の画面を追い出します。これにより、以前に開いた画面を失うことなく、ナビゲーションスタックのメモリ消費を制御できます。

元に戻す/やり直しスタック

元に戻すメカニズム（Undo）はLIFOの古典的な例です。各ユーザーアクションはスタックに保存されます。Undoが呼び出されると、最後のアクションが元に戻され、Redoスタックに移動されます。LIFO Cacheによるスタックサイズの制限により、制限を超えた場合、最も古いアクション（スタックの底）は残り、最新のアクションは破棄されます — これは論理的です。ユーザーは通常、最近のアクションを元に戻し、古いアクションはもはや関連性がないからです。

一時計算バッファリング

バックトラッキングを伴う再帰計算では、中間ステップの結果がLIFO順序で保存されます。バッファがオーバーフローすると、最後の結果が破棄されます — これは許容可能です。必要に応じてアルゴリズムが再計算できるためです。このアプローチはパーサー、コンパイラ、および深さ制限のあるグラフ探索アルゴリズムで使用されます。

LIFO Cacheのコード例

固定サイズ配列を使用したKotlinでのLIFO Cacheの実装を見てみましょう。配列はモバイルデバイスに最適なパフォーマンスと最小限のメモリ消費を提供します。

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を使用したナビゲーションスタック

Jetpack Composeでナビゲーションの深さを制限するためのLIFO Cacheの使用を考えます。新しい画面が開かれるとスタックに追加され、制限を超えると最新の画面が追い出されます。

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が呼び出されると最後の画面が削除されます。ユーザーが10の制限で11画面を開いた場合、最新（11番目）が前（10番目）を追い出します — 最初の画面はスタックに残り、これは戻る移動時のユーザーの期待に一致します。この戦略はナビゲーションにおいてLRUよりも効率的です。長く開かれている画面（「ホーム」、「プロフィール」）を削除すると、予期しない動作につながります。