具体的なアルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/07/02 03:21 UTC 版)
「Least Recently Used」の記事における「具体的なアルゴリズム」の解説
それぞれのエントリごとに、「いつ使用したか」を示すデータを保存する。エントリを使用するごとにそのデータを更新していく。エントリが更新されるタイミングで、それらの時刻を全エントリに対してチェックすると、「最も使用されていないエントリ」が判明する。これが、理想的なLRUアルゴリズムである。しかし、この方法はとても処理に時間がかかる（O(n)）ため、ほとんど使用されない。 多くの場合、処理を簡単化した擬似的なLRUが用いられる。たとえば、すべてのエントリに「最近使用したかどうか」を示すフラグ（dirty flag）を設ける。一度すべてをリセットし、エントリを使用するごとにそのフラグをセットする。一定のタイミング、またはエントリを更新する際にそれらのフラグをチェックすると、「最近使用されていないエントリ」が判明する。適当なタイミングで、またすべてのフラグをリセットする。 これは、完全なLRUではないが、多くの場合非常に近い性能を発揮する。
※この「具体的なアルゴリズム」の解説は、「Least Recently Used」の解説の一部です。
「具体的なアルゴリズム」を含む「Least Recently Used」の記事については、「Least Recently Used」の概要を参照ください。
ウィキペディア小見出し辞書の「具体的なアルゴリズム」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 具体的なアルゴリズムのページへのリンク
