エル‐アール‐ユー【LRU】
LRU
別名：LRU方式
LRUとは、キャッシュアルゴリズムなどで用いられる、置換対象のデータを定める方式のうち、参照されていない時間が最も長いデータを置換対象にする方式のことである。
例えば、仮想記憶管理におけるページング方式では、主記憶装置（メインメモリ）上で補助記憶装置へ退避させるデータ単位（ページ）を選ぶ方式としてLFUを用いることがある。主記憶装置で扱うことのできる容量には限度があるため、主記憶装置の記憶容量を超えるデータを扱う場合は、データの一部を補助記憶装置へと置換することで空き容量を確保する。このとき、LRUでは、それぞれのデータが参照された時間に基づき、その時間が最も古い（least recently）データを置換対象とする。
LRUに対して、LFU（Least Frequently Used）と呼ばれる方式では、データが使用された頻度（frequently）に関する情報に基づき、最も頻度が少なかった情報を置換する。
Least Recently Used
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/03/17 03:23 UTC 版)
Least Recently Used (LRU) とは、データが最後に使われたのはいつであるかを記録し、最近最も使われなかったデータをキャッシュから削除するキャッシュアルゴリズムのこと。CPUのキャッシュメモリや仮想メモリが扱うデータのリソースへの割り当てなどにも使われる。対義語はMost Recently Used (MRU)。
和訳すると「最近最も使われなかったもの」つまり「使われてから最も長い時間が経ったもの」「参照される頻度が最も低いもの」である。
小容量で高速な記憶装置（例えば、CPUのキャッシュメモリ）がいっぱいになったとき、その中にあるデータのうち、未使用の時間が最も長いデータを大容量で低速な記憶装置（例えば、主記憶装置）に保存する、というのが基本のアルゴリズムである。
なお、上の括弧内の例はCPUのキャッシュメモリの場合である。仮想メモリの場合は、小容量で高速な記憶装置を主記憶装置、大容量で低速な記憶装置を補助記憶装置に置き換えればよい。
具体的なアルゴリズム
一般の場合
連結リストと連想配列を組み合わせた物を使用すると（例えばJavaのLinkedHashMap[1]）O(1)の時間計算量で計算が可能である。連想配列により、キャッシュからの取り出しはO(1)であり、参照した際に、連結リストの端に持ってくれば良く、これもO(1)である。キャッシュへの挿入も同様にO(1)である。
CPUのキャッシュメモリの場合
それぞれのエントリごとに、「いつ使用したか」を示すデータを保存する。エントリを使用するごとにそのデータを更新していく。エントリが更新されるタイミングで、それらの時刻を全エントリに対してチェックすると、「最も使用されていないエントリ」が判明する。これが、理想的なLRUアルゴリズムである。しかし、この方法はとても処理に時間がかかる（O(n)）ため、ほとんど使用されない。LinkedHashMapのような手法もCPUのキャッシュメモリとして使用するには計算量が多すぎる。
多くの場合、処理を簡単化した擬似的なLRUが用いられる。たとえば、すべてのエントリに「最近使用したかどうか」を示すフラグ（dirty flag）を設ける。一度すべてをリセットし、エントリを使用するごとにそのフラグをセットする。一定のタイミング、またはエントリを更新する際にそれらのフラグをチェックすると、「最近使用されていないエントリ」が判明する。適当なタイミングで、またすべてのフラグをリセットする。 これは、完全なLRUではないが、多くの場合非常に近い性能を発揮する。
最悪の場合
LRUは、特定のパターンの場合に極端に悪いパフォーマンスを示すことが知られている。たとえば、N個のエントリがある場合に、N+1個のエントリを順番に使用した場合、常にエントリの内容が変更されてしまう。
派生形
単純に最終利用時刻だけでなく、キャッシュに復元する際のコスト（例えば計算結果のキャッシュの場合は再計算にかかる時間）も加味してアルゴリズムを構築する方法などがある。
整理法
LRUは、コンピュータに限らず、野口悠紀雄の『「超」整理法』にも使われている。整理法としては、たとえば、読み終わった本を本棚の一番右側に戻すようにしておくと、左側に読む頻度の少ない本が集まり、処分すべき本を簡単に決めることができる。使われない物が端に押し出されるので、野口悠紀雄はこの手法を押出し法（押出しファイリング）と呼んでいる。[2]
関連項目
参照
- ^ “LinkedHashMap (Java SE 17 & JDK 17)”. docs.oracle.com. 2023年7月4日閲覧。
- ^ 野口悠紀雄『「超」整理法―情報検索と発想の新システム』中央公論新社、1993年11月1日。ISBN 978-4121011596。
- Least Recently Usedのページへのリンク
