LRU アルゴリズム（Least Recently Used）
最も長く使われていないデータを優先的に追い出す置換アルゴリズム
📌LRU とは
LRU（Least Recently Used）とは、キャッシュが満杯になったとき、最も長く使われていない（一番ご無沙汰な）データを優先して追い出す置換アルゴリズムのことです。「置換アルゴリズム＝どのデータを捨てて空きを作るかを決めるルール」のことです。
なぜ「最も長く使われていないもの」を選ぶのでしょうか。それは参照の局所性という経験則に基づいています。参照の局所性＝「最近使ったデータは近いうちにまた使われやすい」という性質のことです。逆に、長く使われていないデータは今後も使われない可能性が高いので、それを捨てるのが合理的、という考え方です。上のツールで▶ボタンを押すと、アクセスのたびに順番が更新され、満杯時に最古が捨てられる様子を確認できます。
身近な例で言うと、机の上に置ける本が3冊までの状況に似ています。新しい本を読みたいのに机が一杯なら、「最近いちばん開いていない本」を本棚に戻しますよね。よく使う本は手元に残り、ご無沙汰な本から片付けていく──これが LRU の発想です。
🔄アルゴリズムの仕組み
LRU は「最近使った順」を常に管理します。データにアクセスするたびに、そのデータを「最も最近使った」位置へ並べ替えるのがポイントです。
アクセス時の動作は3パターンに分かれます。
・ヒット（すでにある）：そのデータを「最新」位置へ移動する。追い出しは起きない
・ミス・空きあり：追い出さず、そのまま読み込んで「最新」位置に追加する
・ミス・満杯：「最古」のデータを1つ追い出し、空いた場所に新しいデータを「最新」位置で入れる
容量3 / アクセス列 A B C A D
─────────────────────
A → [A] （ミス・追加）
B → [B A] （ミス・追加）
C → [C B A] （ミス・追加・満杯に）
A → [A C B] （ヒット・A を最新へ）
D → [D A C] （ミス・満杯 → 最古 B を追い出し）
最後の D のアクセスに注目してください。直前に A を使い直したので、A は「最新」へ移動して残り、代わりに長らく触れられていなかった B が追い出されました。再アクセスのたびに順番を更新することが、LRU が賢く振る舞える理由です。上のツールの「アクセス列」を見ながら、各ステップで順番がどう入れ替わるかを追ってみてください。
⚖️他のアルゴリズムとの比較
追い出すデータを選ぶ置換アルゴリズムには、LRU 以外にもいくつかの方式があります。代表的なものと比べてみましょう。
| 方式 | 追い出す基準 | 特徴 |
|---|---|---|
| LRU | 最も長く使われていないもの | 局所性を活かせる。順序管理のコストが必要 |
| FIFO | 最も古く入れたもの（先入れ先出し） | 実装が簡単。使用頻度を考えない |
| LFU | 最も使用回数が少ないもの | 使用回数を数える。古い人気データが残りがち |
| ランダム | ランダムに選ぶ | 最も単純。性能は運任せ |
特に間違えやすいのがFIFO（First In First Out）との違いです。
・FIFO：入れた順番だけを見る。途中で何度使われても、入った順に追い出す
・LRU：使われた順番を見る。再アクセスされたものは「最新」に更新されて残りやすくなる
上のツールで「FIFOとの違いが出る列」シナリオを選ぶと、A B C のあとに A を再アクセスし、続けて D を入れる場面を試せます。LRU は再アクセスされた A を残して B を追い出しますが、FIFO なら入った順だけを見て一番古い A を追い出してしまいます。「最近使ったかどうかを考慮するのが LRU、入れた順だけを見るのが FIFO」と区別すると分かりやすいです。
💡キャッシュとは何か、なぜ必要か
キャッシュ（cache）とは、よく使うデータをすぐ取り出せる「近くて速い場所」に一時的に保存しておく仕組みのことです。なぜ必要なのでしょうか。
CPUは計算が非常に速いですが、データを取り出すメモリ（主記憶）のアクセスはCPUに比べてずっと遅いという問題があります。もしデータを毎回メモリから取りに行くと、CPUは計算を終えてもメモリの返事を「ぼーっと待つ」ことになります。
そこで登場するのがキャッシュです。「最近・よく使うデータをCPUのそば（高速な記憶域）に控えておき、次にそのデータが必要になったとき一瞬で渡す」のがキャッシュの役割です。
・データがキャッシュにある場合をキャッシュヒット（hit）といい、メモリに取りに行かずに済む
・データがない場合をキャッシュミス（miss）といい、メモリから読み込んでキャッシュに登録する
身近な例で言うと、料理中に調味料を手元の小棚に出しておくのに似ています。毎回遠い倉庫（メモリ）まで取りに行くのは大変なので、よく使うものだけ手元（キャッシュ）に置く。棚が小さいので全部は置けない。だから「最近使ったもの」を優先して残すのが LRU の発想です。
📊ヒット率とLRUの効果
キャッシュの性能を表す指標がヒット率です。ヒット率は次の式で求められます。
ヒット率 = ヒット数 ÷ 総アクセス数
たとえばアクセスが10回あってヒットが8回なら、ヒット率は 8 ÷ 10 ＝ 0.8（80%） です。なぜヒット率を上げることが大切なのでしょうか。それはヒット時とミス時の処理速度が大きく違うからです。
・ヒット時：キャッシュから即座に取得（例：数ナノ秒）
・ミス時：メモリから取得してキャッシュに書き込む（例：数十〜数百ナノ秒）
LRU が「参照の局所性」という性質を活かしているのはここでの話です。最近使ったデータほど近いうちにまた使われる確率が高いため、それを手元に残すと自然とヒット率が上がります。上のツールのシナリオで A B C A というアクセスを見ると、A が2回登場していますが、LRU はそのA を手元に残すので2回目は即座にヒットします。容量が同じでも、置換ルールを賢くするだけでヒット率、そして全体の速度が変わります。
