The MRU List

One of the truisms of search is that if you search for something once, you’re likely to search for it again. In addition, some things are searched for much more often than others. It makes sense, then to cache the results for the most common searches so that you don’t have to query the database or other backing store in order to return results. That way you can satisfy the most common requests very quickly, reducing the load on your back-end database.

The problem, of course, is that you can’t cache all search results. If you could, you wouldn’t need a database to hold the information. The question becomes one of how to determine which results you should store in memory. One method that works very well is the Most Recently Used (MRU) list.

The idea is to keep some small number of the most recently requested results in memory. When somebody performs a search, the program checks the MRU list first. If the results are found in the MRU list, then those results moved to the front of the list. If the requested results are not in the list, then the program queries the database to obtain the results, places those new results at the front of the list, and removes the results from the back of the list--the least recently used results.

Because items are moved back to the front of the list each time they’re requested, the most frequently requested results will remain in the list, and things that are requested infrequently will fall off the back of the list.

This technique works well when searches follow the common pattern: a few terms being much more frequently requested than others. If searches are randomly distributed, the MRU list is not at all affected, because it’s likely that the requested results won’t be in the cache.

The .NET LinkedList class is an excellent choice for implementing an MRU list because moving things around in the list is a constant-time operation. That is, it takes the same amount of time to insert or remove an item in a list of 10,000 items as it does in a list of 10 items.

The MRU List interface requires a way to determine if an item is in the list, and a way to add something to the list. Also, the constructor should let you say how many items the list should hold. That’s really all there is to it, but implementation is just a little bit tricky.

We can build the MRU list as a generic class with two type parameters: the type of object to be stored in the linked list, and the type of key used to search for items. The key is important because the LinkedList.Find method searches the list looking for a particular object reference, rather than a key value. We’ll have to implement our own key search.

The constructor requires two parameters: an integer that specifies the maximum number of items that the MRU list can hold, and a comparison function that can compare a key value against a list object to determine if the object matches the key. The final interface looks like this:


using System;
using System.Collections.Generic;
using System.Text;

namespace MostRecentlyUsedList
{
public delegate bool MruEqualityComparer(K key, T item);

public class MruList
{
private LinkedList items;
private int maxCapacity;
private MruEqualityComparer compareFunc;

public MruList(int maxCap, MruEqualityComparer compFunc)
{
maxCapacity = maxCap;
compareFunc = compFunc;
items = new LinkedList();
}

public T Find(K key)
{
LinkedListNode node = FindNode(key);
if (node != null)
{
items.Remove(node);
items.AddFirst(node);
return node.Value;
}
return default(T);
}

private LinkedListNode FindNode(K key)
{
LinkedListNode node = items.First;
while (node != null)
{
if (compareFunc(key, node.Value))
return node;
node = node.Next;
}
return null;
}

public void Add(T item)
{
// remove items until the list is no longer full.
while (items.Count >= maxCapacity)
{
items.RemoveLast();
}
items.AddFirst(item);
}


}
}


static class Program
{
static private MruList mru;
///

/// The main entry point for the application.
///

[STAThread]
static void Main()
{

mru = new MruList(1000, KeyCompare);

for (int count = 0; count < 1000; count++)
{
mru.Add(new SearchResult("Jim" + count, count));
}
FindItem("Jim999");

}

static private bool KeyCompare(string key, SearchResult item)
{
return key.Equals(item.Name);
}

static private void FindItem(string key)
{
SearchResult rslt = mru.Find(key);
if (rslt == null)
{
Console.WriteLine("’{0}’ not found", key);
}
else
{
Console.WriteLine("’{0}’ is {1}", rslt.Name, rslt.Age);
}

}


}


class SearchResult
{
private string _name;
private int _age;

public SearchResult(string n, int a)
{
_name = n;
_age = a;
}

public string Name
{
get { return _name; }
}

public int Age
{
get { return _age; }
}
}