Is this algorithm implementation LRU or MRU?

Question

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
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.

That's my code. The confusion is in the terminology. Some people say that a cache that keeps the most recently used items is an MRU cache. Others say that MRU means that the most recently used item is discarded. If you do a Google search on "MRU cache", you'll see the term used for both types of caches. If you read the article before the one from which you posted the code, http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=625, you'll see that it's keeping the most recently used items. — Jim Mischel, Feb 25 '14 at 14:26
@JimMischel Got your point. I think I need the latter you said. I will modify code according my need. PS: The code you wrote 11 years ago still provides help to others today, it's amazing! — KyL, Feb 26 '14 at 03:02

score 2 · Answer 1 · answered Feb 25 '14 at 01:34

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.

Caleb · Answer 2 · 2014-02-26T01:41:26.753

1

Based on what is documented here: http://en.wikipedia.org/wiki/Cache_algorithms#Most_Recently_Used

It's LRU. Think about the items being a "ordered" list.

The most recently used item is at the "front". When a new item is added they call items.AddFirst(newNode); which adds it to the front of the list. When an item is "touched", they move it to the front of the list using these calls:

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

When the list is full, it pushes the "last" / "oldest" item from the list using items.RemoveLast();

The cache is removing the "least recently used" items first when it hits capacity.

edited Feb 26 '14 at 01:41

answered Feb 25 '14 at 01:34

Caleb

1,088
7
7

I checked out the conception of MRU from wiki 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." In my opinion, when cache is full, I should remove the front of the list because of the recently accessed node is first node rather than last node. – KyL Feb 25 '14 at 02:59
Looks like you are right (based on the wiki article). For it to be MRU in that standard, it should remove the item on the front of the list, not the back. I'll update my answer. – Caleb Feb 26 '14 at 01:39

score 0 · Answer 3 · answered Nov 22 '18 at 05:24

Microsoft's "MRU" lists correctly use an LRU cache replacement algorithm.

Note that Microsoft in this case uses different terminology for MRU lists than the cache community.

The cache community uses MRU / LRU to talk about replacement (or eviction) strategies. When your cache is full, and you need to put a new item in the list, which item should be removed from the list?

Microsoft provides tools for getting the most recently used items, like for a drop down or a recent documents list.

This means that to correctly implement an MRU list, you need to implement an LRU Cache eviction strategy.

Is this algorithm implementation LRU or MRU?

3 Answers3

Linked