LRUアルゴリズムの原理と実践

概要
オペレーティングシステムでメモリ管理を行う場合、LRU、LFU、FIFOなどのページ置換アルゴリズムが使用されます.ここでLRUは広く応用されている.LRUのフルネームはLeast Recenly Used、すなわち最近最も少ない使用アルゴリズムである.
キャッシュのサイズが限られていることはよく知られていますが、どのようなポリシーに基づいてデータをキャッシュすればいいのでしょうか.LRUは、最近使用されていないデータをキャッシュから削除するという考え方を提供し、実際の環境では常識に合っています.
げんり
LRUアルゴリズムの原理は比較的簡単で、データストレージのデータ構造はチェーンテーブルである.データにアクセスすると、キャッシュにデータがある場合は、チェーンテーブルの先端にデータを移動します.データがない場合は、先頭にデータを追加し、チェーンテーブルの下端のデータを削除します.
LRUは、キャッシュにデータが見つからないかどうかという概念に関連しています.
ページサイズが3、シーケンスが4、3、2、3、5の場合、次の欠落回数は4回です.
4
3
2
3
5
4
3
2
3
5
null
4
3
2
3
null
null
4
4
2
ページが切れる
ページが切れる
ページが切れる
欠かさない
ページが切れる
コード実装
LRUアルゴリズムの原理は簡単であるが、実現は複雑であり、特にページの置換を処理する場合、JavaにおけるLinkedHashMapのアクセス秩序性はLRUのニーズを適切に満たす.以下、LeetCode第146題により、アルゴリズムの実装手順を説明する.
サンプル:
時間的複雑度がO(1)の操作を実現

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

コード実装

public class LRUCache {
    private LinkedHashMap map;
    private final int CAPACITY;
    public LRUCache(int capacity) {
        CAPACITY = capacity;
        map = new LinkedHashMap(capacity, 0.75f, true){
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > CAPACITY;
            }
        };
    }
    public int get(int key) {
        return map.getOrDefault(key, -1);
    }
    public void put(int key, int value) {
        map.put(key, value);
    }
}