该算法是LRU还是MRU? [英] Is this algorithm implementation LRU or MRU?

问题描述

我正在使用C#在我的项目中实现MRU(最近使用最多)缓存.

我用Google搜索了有关MRU的一些概念和实现，而与之相反的是LRU(最近最少使用)，发现这篇文章

I am working on implementing a MRU(Most Recently Used) cache in my project using C#.

I googled some conceptions and implementations about MRU, and its contrary, LRU(Least Recently Used), and found this article http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=626 that describes the implementation of MRU collection in C#.

To confuse me is that I think this implementation is LRU rather than MRU. Could anyone help me to confirm this collection class is MRU or not?

Following code block is the whole MRUCollection class. Thanks.

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相比，首先丢弃最近使用的物品.

据我了解，由于最近访问的节点已移到列表的最前面，因此如果缓存已满，我们应该删除列表的第一个节点而不是最后一个节点.

---

http://en.wikipedia.org/wiki/Cache_algorithms#Most_Recently_Used
Most Recently Used (MRU): discards, in contrast to LRU, the most recently used items first.

According my understanding, as the node accessed recently is moved to the front of list, if the cache is full, we should remove the first node of list rather than last.

推荐答案

在我看来，它像是MRU实现.请注意，搜索是如何从链接列表的开头开始并返回的，每当访问一个节点时，它就会移到列表的前面.在Add()中，使用AddFirst()添加该节点，而在TryGetValue()中，它删除该节点并将其添加到列表的前面.

It looks to me like an MRU implementation. Notice how searches start from the beginning of the linked list and go back, and whenever a node is accessed it's moved to the front of the list. In Add(), the node is added using AddFirst(), and in TryGetValue(), it removes the node and adds it to the front of the list.

这篇关于该算法是LRU还是MRU?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！