読み方：エルエフユー

LFU【Least Frequently Used】

概要

LFUとは、キャッシュメモリや仮想メモリなどで用いられるデータ置換アルゴリズムの一つで、限られた記憶領域が満杯になった際に、それまでの参照回数が最も少ないデータを削除して新しいデータを格納する方式。

CPUのキャッシュメモリやオペレーティングシステム（OS）の仮想メモリ（仮想記憶）では、高速だが容量の小さい記憶領域を使い回して処理に必要なデータを用意する。新たなデータを書き込む空きがなくなると、一定のアルゴリズムに従って既存のデータを削除するか、より低速・大容量な記憶装置へ追い出し、空いた領域を確保する。

LFUでは、キャッシュ内の各データについてアクセス回数を記録し続け、入れ替えが必要になった時点でカウントが最小、すなわち「最もアクセスされていない」データを削除対象とする。参照回数が同数のデータが複数あるときは、最後にアクセスした時刻が古いものを優先して削除するのが一般的である。

LFUと対比される置換アルゴリズムに「LRU」（Least Recently Used）がある。これは最後に参照した時刻を基準とし、「最も長く使われていない」データを破棄する。LFUが過去の累積的な利用頻度を重視するのに対し、LRUは直近の利用状況を重視する。長期に渡って安定して参照されるデータを保持しやすいのがLFUであり、直近のアクセスを反映しやすいのがLRUである。CPUのキャッシュメモリ、データベースのバッファ管理、Webサーバのコンテンツキャッシュなど、様々な場面でいずれかが選択される。

LFUの難点として、過去に参照回数が積み上がったデータが、現在ほとんど使われなくなっても領域を占有し続けやすい点がある。アクセス回数は累積するため、最近になって利用頻度が高まったデータが古い高頻度データを追い越すには時間がかかる。この問題に対処するため、一定期間ごとにカウントを減衰させる手法や、直近のアクセスに重みを加える改良アルゴリズムも考案されている。

(2026.6.3更新)