頭脳一式

人の記憶なんて曖昧なもの。すべての情報を頭に記憶するなんてナンセンス。困ったらここに来ればいいじゃん?というスタンスで最強のナレッジベースを目指すブログ

【アルゴリズム】LRU(Least Recently Used)の実装

LRUとは

www.weblio.jp

要するに、一番使われていないものを捨てて、新しいものと入れ替える方式のこと。

JavaでLRU(Least Recently Used)を実装してみる

今回は、最大で保持できる要素数は5個までとし、6個目の要素を格納したときに、
一番使われていない要素を捨てて6個目の要素を入れるような処理を目指します。

1.要素を5個まで保持できるLinkedHashMapの生成方法

まず、「最大で保持できる要素が5個まで」という仕組みを作ります。
具体的にはLinkedHashMapのremoveEldestEntryメソッドをオーバーライドし、
「return size() > 5;」とします。

public static void main(String[] args) {
    //↓↓インナークラスここから↓↓
    class LRU5 extends LinkedHashMap<String, String> {
        protected boolean removeEldestEntry(Map.Entry eldest) {
            return size() > 5;
        }
    }
    //↑↑インナークラスここまで↑↑

    tryLRU(new LRU5());
}

private static void tryLRU(Map map) {
    map.put("Amazon", "11111");
    map.put("Apple", "22222");
    map.put("MicroSoft", "33333");
    map.put("TOYOTA", "44444");
    map.put("NISSAN", "55555");
    System.out.println("5個目:" + map);

    map.put("Tesla", "66666");
    System.out.println("6個目追加:" + map);
}

実行すると以下の2行が出力されます。
5個目:{Amazon=11111, Apple=22222, MicroSoft=33333, TOYOTA=44444, NISSAN=55555}
6個目追加:{Apple=22222, MicroSoft=33333, TOYOTA=44444, NISSAN=55555, Tesla=66666}

removeEldestEntryはTrueを返すたびに、Mapの先頭の要素を削除します。
前後の出力結果を見比べると6個目のTeslaを追加された代わりに1個目のAmazonが無くなっていることが分かります。
これで「最大で保持できる要素が5個まで」という仕組みは完成です。

2.LinkedHashMapをアクセス順で要素を保持するMapにする方法

次に、「一番使われていない要素」を判定するためにMapをアクセス順に保持する必要があります。
インナークラスのインスタンスを生成する際の引数を以下のようにします。

new LRU5(5, 0.75f, true));

3.完成版ソース

前述の1と2を組み合わせて以下のようなソースにするとLRUとして機能します。

public static void main(String[] args) {

    //↓↓インナークラスここから↓↓
    class LRU5 extends LinkedHashMap<String, String> {
        LRU5(int i, float f, boolean b){
            super(i, f, b);
        }
        protected boolean removeEldestEntry(Map.Entry eldest) {
            return size() > 5;
        }
    }
    //↑↑インナークラスここまで↑↑

    tryLRU(new LRU5(5, 0.75f, true));
}

private static void tryLRU(Map map) {
    map.put("Amazon", "11111");
    map.put("Apple", "22222");
    map.put("MicroSoft", "33333");
    map.put("TOYOTA", "44444");
    map.put("NISSAN", "55555");
    System.out.println("アクセス前:" + map);
    map.get("Amazon");
    map.put("Tesla", "66666");
    System.out.println("アクセス後:" + map);
}

4.実行結果の解説

実行すると以下の2行が出力されます。
アクセス前:{Amazon=11111, Apple=22222, MicroSoft=33333, TOYOTA=44444, NISSAN=55555}
アクセス後:{MicroSoft=33333, TOYOTA=44444, NISSAN=55555, Amazon=11111, Tesla=66666}

put処理は要素アクセスしたと見做されるのでputした順に要素アクセスしたことになります。
5個putした時点では、一番最後にputした要素がNISSANなので一番最後にアクセスした要素もNISSANとなります。
ですが、 次の行でAmazonをgetしています。get処理もput処理と同様に要素にアクセスしたと見做されるため、この処理により一番最後にアクセスした要素がAmazonに変わります。
このタイミングでTeslaをputすると、アクセス順が若い要素(最も使われていない要素)はAppleとなるので、Appleが消え、代わりにTeslaが格納される結果となります。