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

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

目次へ

LRUとは

www.weblio.jp

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

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

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

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

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

Java

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行が出力されます。

Java

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個まで」という仕組みは完成です。

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

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

Java

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

３．完成版ソース

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

Java

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);
}

４．実行結果の解説

実行すると以下の2行が出力されます。

Java

アクセス前：{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が格納される結果となります。