这个算法的实现是LRU还是MRU？

Question

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

我在谷歌上搜索了一些关于MRU的概念和实现，以及与之相反的LRU(最近最少使用的)，并找到了这篇文章http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=626，它描述了C#中MRU集合的实现。

让我困惑的是，我认为这个实现是LRU而不是MRU。有没有人能帮我确认一下这个采集类是不是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相比，首先丢弃最近使用的项目。

​

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

​

Answer 1

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

Answer 2

基于这里的文档：http://en.wikipedia.org/wiki/Cache_algorithms#Most_Recently_Used

是LRU。把items想象成一个“有序”列表。

最近使用的项目在“前面”。当添加新项时，它们调用items.AddFirst(newNode);，将其添加到列表的前面。当一个项目被“触摸”时，他们使用这些调用将它移到列表的前面：

items.Remove(node);
items.AddFirst(node);

当列表已满时，它使用items.RemoveLast();推送列表中的“最后”/“最旧”项

当达到容量时，缓存将首先删除“最近最少使用”的项目。

Answer 3

Microsoft的"MRU“列表正确地使用了LRU缓存替换算法。

请注意，在这种情况下，Microsoft对MRU列表使用的术语与缓存社区不同。

缓存社区使用MRU / LRU来讨论替换(或驱逐)策略。当缓存已满，并且需要在列表中添加新项时，应该从列表中删除哪一项？

Microsoft提供了获取最近使用的项目的工具，如下拉列表或最近使用的文档列表。

• https://docs.microsoft.com/en-us/windows-hardware/drivers/install/mru-source-list-functions
• https://www.codeproject.com/articles/78/most-recently-used-list-in-a-combobox

这意味着要正确实现MRU列表，您需要实现LRU缓存逐出策略。