LRUキャッシュ

Least Recently Used cache

最近使用順キャッシュ

キャッシュのリスト内に目的のレコードが見つからなかった場合は、そのレコードを実データから読み出して、キャッシュのリストの先頭に追加する。

リストが溢れる場合は、リストの中で最も最古のレコード(=最後部)を破棄する。

リスト内で見つかった場合は、そのレコードをリストの先頭に移動する。

メリット

キャッシュサイズが明確

キャッシュ内検索に辞書構造を導入しなくても、単純な線形探索アルゴリズムよりは少し早いことが期待される。

ヒットしやすいものは前方に集中するため。

デメリット

大量データを取り込んでキャッシュがあふれると、キャッシュ能力を失う。

関連