[解決済み] LFU（Least Frequently Used）キャッシュを実装するには？

質問

LFU（Least Frequently Used）とは、コンピュータ内のメモリを管理するためのキャッシュアルゴリズムの一種である。この方法の標準的な特徴は、システムがメモリ内でブロックが参照された回数を追跡することです。キャッシュが満杯になり、さらにスペースが必要になると、システムは参照回数が最も少ないものをパージする。

オブジェクトの最近使ったキャッシュを実装するには、例えばJavaでどのような方法が良いでしょうか？

私はすでにLinkedHashMap（オブジェクトへのアクセス回数を管理する）を使用して1つを実装しました。

キャッシュが満杯になり、別のキャッシュのためのスペースを確保する必要があるとします。キャッシュには2つのオブジェクトが記録されており、それらは1回だけアクセスされる。 もう一つのオブジェクト（キャッシュにない）が複数回アクセスされていることがわかったら、どちらを削除すればいいでしょうか？

ありがとうございます。

解決方法は？

1. 私によれば、最も最近使われたオブジェクトのキャッシュを実装する最良の方法は、各オブジェクトに 'latestTS' として新しい変数を含めることです。TSはタイムスタンプを意味します。

   // 1970年1月1日からのミリ秒単位で現在の日時を返すスタティックメソッドです。 long latestTS = System.currentTimeMillis()。

2. ConcurrentLinkedHashMap は Concurrent Java Collections にまだ実装されていません。 (参考 Java コンカレントコレクション API ). しかし、試しに コンカレントハッシュマップ と ダブリーリンクリスト

3. このような場合、latestTS変数を宣言しておけば、latestTS変数の値に基づいて、エントリーを削除し、新しいオブジェクトを追加することができると述べましたが、いかがでしょうか。(追加された新しいオブジェクトの頻度とlatestTSを更新することを忘れないでください。）

ご指摘の通り LinkedHashMap これは、O(1)で要素にアクセスでき、また、順序のトラバーサルを得ることができるからです。 LFU Cacheについては、以下のコードをご覧ください。 (PS: 以下のコードは、タイトルにある質問、すなわち "How to implement LFU cache" に対する答えです)

import java.util.LinkedHashMap;
import java.util.Map;

public class LFUCache {

    class CacheEntry
    {
        private String data;
        private int frequency;

        // default constructor
        private CacheEntry()
        {}

        public String getData() {
            return data;
        }
        public void setData(String data) {
            this.data = data;
        }

        public int getFrequency() {
            return frequency;
        }
        public void setFrequency(int frequency) {
            this.frequency = frequency;
        }       

    }

    private static int initialCapacity = 10;

    private static LinkedHashMap<Integer, CacheEntry> cacheMap = new LinkedHashMap<Integer, CacheEntry>();
    /* LinkedHashMap is used because it has features of both HashMap and LinkedList. 
     * Thus, we can get an entry in O(1) and also, we can iterate over it easily.
     * */

    public LFUCache(int initialCapacity)
    {
        this.initialCapacity = initialCapacity;
    }

    public void addCacheEntry(int key, String data)
    {
        if(!isFull())
        {
            CacheEntry temp = new CacheEntry();
            temp.setData(data);
            temp.setFrequency(0);

            cacheMap.put(key, temp);
        }
        else
        {
            int entryKeyToBeRemoved = getLFUKey();
            cacheMap.remove(entryKeyToBeRemoved);

            CacheEntry temp = new CacheEntry();
            temp.setData(data);
            temp.setFrequency(0);

            cacheMap.put(key, temp);
        }
    }

    public int getLFUKey()
    {
        int key = 0;
        int minFreq = Integer.MAX_VALUE;

        for(Map.Entry<Integer, CacheEntry> entry : cacheMap.entrySet())
        {
            if(minFreq > entry.getValue().frequency)
            {
                key = entry.getKey();
                minFreq = entry.getValue().frequency;
            }           
        }

        return key;
    }

    public String getCacheEntry(int key)
    {
        if(cacheMap.containsKey(key))  // cache hit
        {
            CacheEntry temp = cacheMap.get(key);
            temp.frequency++;
            cacheMap.put(key, temp);
            return temp.data;
        }
        return null; // cache miss
    }

    public static boolean isFull()
    {
        if(cacheMap.size() == initialCapacity)
            return true;

        return false;
    }
}