3

C# を使用してプロジェクトに MRU (最近使用した) キャッシュを実装する作業を行っています。

MRU とその反対である LRU (最近使用されていない) に関するいくつかの概念と実装をグーグルで調べたところ、次の記事を見つけましたhttp://www.informit.com/guides/content.aspx?g=dotnet&seqNum=626の実装について説明していますC# での MRU コレクション。

私を混乱させるのは、この実装が MRU ではなく LRU だと思うことです。このコレクション クラスが MRU であるかどうかを確認するのを手伝ってくれる人はいますか?

次のコード ブロックは、MRUCollection クラス全体です。ありがとう。

class MruDictionary<TKey, TValue>
{
    private LinkedList<MruItem> items;
    private Dictionary<TKey, LinkedListNode<MruItem>> itemIndex;
    private int maxCapacity;
    public MruDictionary(int cap)
    {
        maxCapacity = cap;
        items = new LinkedList<MruItem>();
        itemIndex = new Dictionary<TKey, LinkedListNode<MruItem>>(maxCapacity);
    }
    public void Add(TKey key, TValue value)
    {
        if (itemIndex.ContainsKey(key))
        {
            throw new ArgumentException("An item with the same key already exists.");
        }
        if (itemIndex.Count == maxCapacity)
        {
            LinkedListNode<MruItem> node = items.Last;
            items.RemoveLast(); //Why do we move the last than first here? The node accessed recently is moved to the front of list.
            itemIndex.Remove(node.Value.Key);
        }
        LinkedListNode<MruItem> newNode = new LinkedListNode<MruItem>(new MruItem(key, value));
        items.AddFirst(newNode);
        itemIndex.Add(key, newNode);
    }
    public bool TryGetValue(TKey key, out TValue value)
    {
        LinkedListNode<MruItem> node;
        if (itemIndex.TryGetValue(key, out node))
        {
            value = node.Value.Value;
            items.Remove(node);
            items.AddFirst(node);
            return true;
        }
        value = default(TValue);
        return false;
    }
}

class MruItem
{
    private TKey _key;
    private TValue _value;
    public MruItem(TKey k, TValue v)
    {
        _key = key;
        _value = v;
    }
    public TKey Key
    {
        get { return _key; }
    }
    public TValue Value
    {
        get { return _value; }
    }
}

http://en.wikipedia.org/wiki/Cache_algorithms#Most_Recently_Used
最近使用した (MRU): LRU とは対照的に、最近使用したアイテムを最初に破棄します。

私の理解では、最近アクセスしたノードがリストの先頭に移動されるため、キャッシュがいっぱいの場合は、リストの最後ではなく最初のノードを削除する必要があります。

4

3 に答える 3

0

Microsoft の「MRU」リストは、LRU キャッシュ置換アルゴリズムを正しく使用しています。

この場合、Microsoft はキャッシュ コミュニティとは異なる MRU リストの用語を使用していることに注意してください。

キャッシュ コミュニティは、MRU / LRU を使用して、置換(または削除) 戦略について話します。キャッシュがいっぱいになり、リストに新しい項目を追加する必要がある場合、どの項目をリストから削除する必要がありますか?

Microsoft は、ドロップダウンや最近使用したドキュメント リストなど、最近使用したアイテムを取得するためのツールを提供しています。

これは、MRU リストを正しく実装するには、LRU キャッシュのエビクション戦略を実装する必要があることを意味します。

于 2018-11-22T05:24:13.703 に答える