3

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

我在 Google 上搜索了一些关于 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 相比，首先丢弃最近使用的项目。

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

4

3 回答 3

2

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

于 2014-02-25T01:34:27.180 回答
1

根据此处记录的内容：http ://en.wikipedia.org/wiki/Cache_algorithms#Most_Recently_Used

是LRU。想想这items是一个“有序”的列表。

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

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

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

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

于 2014-02-25T01:34:34.950 回答
0

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

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

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

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

这意味着要正确实现一个 MRU 列表，需要实现一个 LRU Cache eviction 策略。

于 2018-11-22T05:24:13.703 回答