7

を実装したいのですがLRU cache、最近使用されていない要素が非同期で削除されます。私の現在のアイデアは、を使用しDictionaryてペアを格納し<key,value>、オブジェクトへのアクセス時間を追跡し、を保持することSortedDictionary <key, timestamp>です。非同期スレッドがからLRUアイテムを取得しSortedDictionary、キャッシュから削除するという考え方です。しかし、これが機能SortedDictionaryするためには、値でソートする必要がありますが、そうではありません。

{キーとタイムスタンプ}をタイムスタンプでソートしたままSortedListにするために、の代わりに別の方法を使用することもできますが、リストからキーを見つけるために「線形」ルックアップを実行する必要があります（タイムスタンプを更新する必要がある場合） SortedDictionary、同じキーに再度アクセスした場合）-可能であれば、線形よりも優れた方法を探しています。誰かがこの問題に対処するためのアイデアを共有できますか？

だから、私の問題はこれに要約されます：

タイムスタンプを更新するために<=logn時間でキーを検索すると同時に、タイムスタンプに基づいてソートされたキーを取得する必要があります。

考えられる1つの方法は、{key、timestamp}のタイムスタンプ部分に基づいてキーを並べ替える方法を維持することSortedDictionaryでした。<{key,timestamp},null>これは問題ありませんが、問題はhashcode()key.hashcode（）（タイムスタンプの更新中のルックアップ用）を返す必要があることですが、タイムequals()スタンプも使用する必要があります。だから、equals()そしてhashcode()対立しているので、これは良い考えではないと感じました...

4

4 に答える 4

4

あなたがすべきことは、2つの辞書を保持することです。1つは時間でソートされ、もう1つはキーでソートされます。

ディクショナリは実際のオブジェクトへの参照のみを保持しているため、オブジェクトの更新にどのディクショナリを使用するかは重要ではないことに注意してください。

オブジェクトを更新するには、両方の辞書を更新する関数を作成します

var oldObj = keyedObject[key];
timedObjects.Remove(oldObj.LastUpdateTime);
timedObjects.Add(myUpdatedObject.LastUpdateTime,myUpdatedObject);
keyedObject[key] = myUpdatedObject;

これで、時間とキーの両方で同じオブジェクトを追跡できます。

内のオブジェクトへの参照を1つだけ保持していますtimedObjects。これは、削除するときに役立ちます。

必要に応じて、timedObjectsディクショナリをトリミングし続けることができます。

多くの場合、トリミング中はkeyedObject、同じオブジェクトを参照する別の辞書があることに注意する必要があります。ただ電話Removeするだけでは十分ではありません。

削除コードは次のようにする必要があります。

removeObject = timedObjects[timeToRemove];
timedObjects.Remove(timeToRemove);
keyedObject.Remove(removeObject.key);

timeToRemoveは、ほとんどの場合、削除するオブジェクトを決定するforループから取得されます。

于 2012-07-26T12:17:19.397 に答える
0

探しているマップのタイプは（少なくともJavaでは）と呼ばれますLinkedHashMap。

javadocから：

予測可能な反復順序を使用した、マップインターフェイスのハッシュテーブルとリンクリストの実装。この実装は、すべてのエントリを介して実行される二重リンクリストを維持するという点でHashMapとは異なります。このリンクリストは、反復順序を定義します。これは通常、キーがマップに挿入された順序（挿入順序）です。

リンクされたハッシュマップを作成するための特別なコンストラクターが提供されます。その反復の順序は、エントリが最後にアクセスされた順序であり、最近アクセスされた順序から最近アクセスされた順序（access-order）までです。この種のマップは、LRUキャッシュの構築に最適です。

LinkedHashMapOpenJDKからのソース

AFAIK、LinkedHashMapC＃には既存の実装はありません。そうは言っても、それを書くのはそれほど難しいことではないはずです。

于 2012-07-26T12:28:12.943 に答える
0

ソートされた辞書の代わりに、独自のリンクリストを作成し、辞書がそのノードを値として指すようにします。これは常にタイムスタンプでソートされ、タイムスタンプを更新し、最も使用頻度の低い要素を削除するとO（1）になります。

于 2012-07-26T12:35:34.603 に答える
0

これがc＃でのLRUキャッシュの実装です。効率的なO（1）ですが、スレッドセーフではありません。

    static void Main(string[] args)
    {
        var cache = new LruCache(3);
        cache.Put(1, 1);
        cache.Put(2, 2);
        Console.WriteLine(cache.Get(1));       // returns 1
        cache.Put(3, 3);    // evicts key 2
        Console.WriteLine(cache.Get(2));       // returns -1 (not found)
        cache.Put(4, 4);    // evicts key 1
        Console.WriteLine(cache.Get(1));       // returns -1 (not found)
        Console.WriteLine(cache.Get(3));       // returns 3
        Console.WriteLine(cache.Get(4));       // returns 4     

    }

    public class DoubleLinkedList
    {
        public int key;
        public int value;
        public DoubleLinkedList next;
        public DoubleLinkedList prev;
        public DoubleLinkedList(int k, int v)
        {
            key = k;
            value = v;
        }
    }

    public class LruCache
    {
        private int size;
        private int capacity;
        private Dictionary<int, DoubleLinkedList> map;
        private DoubleLinkedList head;
        private DoubleLinkedList tail;
        public LruCache(int cap)
        {
            capacity = cap;
            map = new Dictionary<int, DoubleLinkedList>();
            head = new DoubleLinkedList(0, 0);
            tail = new DoubleLinkedList(0, 0);
            head.next = tail;
            tail.prev = head;
        }

        public int Get(int key)
        {
            if (map.ContainsKey(key))
            {
                if (tail.prev.key != key)
                {
                    var node = map[key];
                    RemoveNode(node);
                    AddToEnd(node);
                }
                return map[key].value;
            }
            return -1;
        }

        private void AddToEnd(DoubleLinkedList node)
        {
            var beforeTail = tail.prev;
            node.prev = beforeTail;
            beforeTail.next = node;
            tail.prev = node;
            node.next = tail;
        }

        private void RemoveNode(DoubleLinkedList node)
        {
            var before = node.prev;
            before.next = node.next;
            node.next.prev = before;
        }

        public void Put(int key, int value)
        {
            if (map.ContainsKey(key))
            {
                map[key].value = value;
                var node = map[key];
                RemoveNode(node);
                AddToEnd(node);
            }
            else
            {
                size++;
                if (size > capacity)
                {
                    var node = head.next;
                    RemoveNode(node);
                    map.Remove(node.key);
                    size--;
                }

                var newNode = new DoubleLinkedList(key, value);
                AddToEnd(newNode);
                map.Add(key, newNode);
            }
        }
    }
于 2019-03-11T04:11:26.003 に答える