这个算法实现是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相反，先丢弃最近使用的项。

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

- KyL

---

这是我的代码。混淆在术语上。有些人说，保留最近使用的项目的高速缓存是MRU高速缓存。其他人则表示MRU表示最近使用的项目已被丢弃。如果您在Google上搜索“MRU高速缓存”，您将看到该术语用于两种类型的高速缓存。如果您在发布代码之前阅读了文章http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=625，您将看到它正在保留最近使用的项目。 - Jim Mischel

@JimMischel 懂了，我需要后者。我会根据我的需求修改代码。顺便说一句，你11年前写的那段代码今天仍然为他人提供帮助，太神奇了！ - KyL

Answer 1

我认为这是一种最近最少使用（MRU）的实现方式。注意搜索是从链表开头开始向后进行的，每当访问一个节点时，它就会被移动到链表的前面。在Add()中，节点是使用AddFirst()添加的，在TryGetValue()中，它会将节点删除并添加到链表的前面。

- user3288049

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();将“最后一个”/“最旧的”项目从列表中推出。

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

- Caleb

---

我从维基百科http://en.wikipedia.org/wiki/Cache_algorithms#Most_Recently_Used了解到MRU的概念：“最近最少使用（MRU）算法与LRU相反，会先淘汰最近访问的项目。” 我认为当缓存已满时，应该删除列表的前面，因为最近访问的节点是第一个节点而不是最后一个节点。 - KyL

看起来你是对的（基于维基百科文章）。为了符合该标准的MRU，它应该删除列表前面的项目，而不是后面的。我会更新我的答案。 - Caleb

Answer 3

微软的“MRU”列表正确使用了LRU缓存替换算法。

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

缓存社区使用MRU / LRU来讨论替换（或驱逐）策略。当您的缓存已满，并且需要将新项目放入列表中时，应从列表中删除哪个项目？

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

• https://learn.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缓存逐出策略。

- McKay