C# Sorted List by Value with Object

Question

I'm trying to create an "ordered" cache of objects in C#, where the order is determined by how many times that has been accessed.

I've looked into Dictionary, SortedList and SortedDictionary which were very close but don't quite have what I'm looking for.

I'd like to have a list which contains all the previously cached items, those items can have a getHits() method to determine what order the cached items should be in.

I can then access that cache by name and increase how many times an item has been viewed.

Simplified example (in Pseudo C#):

class Result {
  public int Hits = 0;
  public string Name = "";

  public void IncreaseHits() {
    this.hits++;
  }

  public Result(String name) {
    this.name = name;
  }
}

class Program {
  public MagicSortableType<string, Result> MyCache; //what structure to use?


  public main() {
    MyCache.Add(new Result("My result 1"));
    MyCache.Add(new Result("My result 2"));
    MyCache.Add(new Result("My result 3"));

    MyCache['My result 2'].IncreaseHits();
    MyCache['My result 2'].IncreaseHits();
    MyCache['My result 3'].IncreaseHits();

    MyCache.SortDesc(); //what is the real C# equivalent?

    foreach(Result result in MyCache) {
      Console.Write(result.Name + " - hits " + result.Hits);
    }
  }
}

Outputs:

My result 2 - hits 2
My result 3 - hits 1
My result 1 - hits 0

Answer 1

When I needed something like this, I created what I called an MruDictionary. It consisted of a LinkedList<T>, and a Dictionary<string, LinkedListNode<T>> (where T is the type of object, and the object key was type string).

Access is through the dictionary. When an item is accessed, it is moved to the head of the list. When an item is added, it's added to the head of the list. If the list size grows beyond the set maximum, the last node in the list is removed.

This worked very well. The items weren't kept in order by number of times used, but rather in strict MRU order. This typically kept the most often used items in the cache, but if there was a long period in which a popular item wasn't used, it would get flushed. For my purposes this worked very well.

I wrote an article about it. Full source with description is available at http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=626.

It should be easy enough to add the hit count if you really need it.

Answer 2

Building upon your pseudo code, this seems to be working:

var MyCache = new Dictionary<string, Result>
{
    {"My result 1", new Result("My result 1")},
    {"My result 2", new Result("My result 2")},
    {"My result 3", new Result("My result 3")},
    {"My result 4", new Result("My result 4")}
};

MyCache["My result 2"].IncreaseHits();
MyCache["My result 2"].IncreaseHits();
MyCache["My result 3"].IncreaseHits();

foreach (var result in MyCache.OrderByDescending(x => x.Value.Hits))
{
    Console.WriteLine(result.Value.Name + " - hits " + result.Value.Hits);
}

Answer 3

I guess you need something like:

SortedDictionary<string,int> MyCache = new SortedDictionary<string, int>();
string strKey = "NewResult";
if (MyCache.ContainsKey(strKey))
{
    MyCache[strKey] = MyCache[strKey] + 1;
}
else
{
    MyCache.Add(strKey, 1);
}

But SortedDictionary is sorted on the key

SortedDictionary - MSDN

Represents a collection of key/value pairs that are sorted on the key.

You can extract the dictionary to List<KeyValuePair<string,int>> and then sort them based on teh value like:

List<KeyValuePair<string, int>> list = MyCache.ToList();
foreach (var item in list.OrderByDescending(r=> r.Value))
{
    Console.WriteLine(item.Key+ " - hits " + item.Value);
} 

So you can have:

class Program
{
    public static SortedDictionary<string, int> MyCache = new SortedDictionary<string, int>();
    static void Main(string[] args)
    {

        AddToDictionary("Result1");
        AddToDictionary("Result1");
        AddToDictionary("Result2");
        AddToDictionary("Result2");
        AddToDictionary("Result2");
        AddToDictionary("Result3");

        List<KeyValuePair<string, int>> list = MyCache.ToList();
        foreach (var item in list.OrderByDescending(r=> r.Value))
        {
            Console.WriteLine(item.Key+ " - hits " + item.Value);
        } 


    }
    public static void AddToDictionary(string strKey)
    {
        if (MyCache.ContainsKey(strKey))
        {
            MyCache[strKey] = MyCache[strKey] + 1;
        }
        else
        {
            MyCache.Add(strKey, 1);
        }
    }
}

Then the output would be:

Result2 - hits 3
Result1 - hits 2
Result3 - hits 1

Answer 4

Wonder if you are after something like this.

You could store two sets of relationships; all the objects, by key to make retrieval fast, and all of the objects by Hits to store the ordering. This has the added advantage of speeding up access - you can get the Result, the Hits, and therefore it's current and next index quite quickly.

When Getting a result, we lock the access to ensure we change it's order atomically, then return the object. We also cheat when writing out the number of hits; we know what the most popular is and then we can just walk backwards through that collection - could really even extract the keys to a List<Int32>, sort it, then iterate through that.

public class PopularityContest{

    private Dictionary<int, List<Result>> PopularityContainer { get; set; }

    private Dictionary<String, Result> ResultContainer { get; set; }

    private int MaxPopularity = 0;

    public PopularityContest(){
        PopularityContainer = new Dictionary<int, List<Result>>();
        ResultContainer = new Dictionary<String, Result>();
    }

    private Object _SyncLock = new Object();

    public Result GetResult(string resultKey)
    {

      Result result = ResultContainer[resultKey];

      lock(_SyncLock)
      {

        int currentHits = result.Hits;

        if(PopularityContainer.ContainsKey(currentHits) && PopularityContainer[currentHits].Contains(result))
        {
           PopularityContainer[currentHits].Remove(result);
        }

        if(!PopularityContainer.ContainsKey(currentHits + 1))
        {
          PopularityContainer.Add(currentHits + 1, new List<Result>());
        }

        PopularityContainer[currentHits + 1].Add(Result);

        if((currentHits + 1) > MaxPopularity) { MaxPopularity = currentHits + 1;}

      }

      return result;

    }


    public void WritePopularity()
    {

      //Here could also extract the keys to a List<Int32>, sort it, and walk that.
      //Note, as this is a read operation, dependent upon ordering, you would also consider locking here.

      for(int i = MaxPopularity; i >= 0; i--)
      {
         if(PopularityContainer.Contains(i) && PopularityContainer[i].Count > 0)
         {
            //NB the order of items at key[i] is the order in which they achieved their popularity
            foreach(Result result in PopularityContainer[i])
            {
            Console.WriteLine(String.Format("{0} has had {1} hits", result.ToString(), i));
            }
         }

      }
    }

}

Answer 5

The Cache below exposes a simple Add/Get interface for adding and retrieving items from the cache, which could obviously be improved upon. It implements IEnumerable, which enumerates through the cache with the required behaviour. There are obviously threading issues here that would need to be addressed.

public class Cache<T>: IEnumerable<T>
{
    //Dictionary to hold the values of the cache
    private Dictionary<string, T> m_cacheStore = new Dictionary<string, T>();

    //Dictionary to hold the number of times each key has been accessed
    private Dictionary<string, int> m_cacheAccessCount = new Dictionary<string, int>(); 

    public T Get(string cacheKey)
    {
        if (m_cacheStore.ContainsKey(cacheKey))
        {
            //Increment access counter
            if (!m_cacheAccessCount.ContainsKey(cacheKey))
                m_cacheAccessCount.Add(cacheKey, 0);
            m_cacheAccessCount[cacheKey] = m_cacheAccessCount[cacheKey] + 1;

            return m_cacheStore[cacheKey];
        }
        throw new KeyNotFoundException(cacheKey);
    }

    public int GetHits(string cacheKey)
    {
        return m_cacheAccessCount.ContainsKey(cacheKey) ? m_cacheAccessCount[cacheKey] : 0;
    }

    public void Add(string cacheKey, T cacheValue)
    {
        if(m_cacheStore.ContainsKey(cacheKey))
            throw new ArgumentException(string.Format("An element with the key {0} already exists in the cache", cacheKey));
        m_cacheStore.Add(cacheKey, cacheValue);
    }

    #region Implementation of IEnumerable

    public IEnumerator<T> GetEnumerator()
    {
        foreach (var source in m_cacheAccessCount.OrderBy(kvp => kvp.Value))
        {
            yield return m_cacheStore[source.Key];
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    #endregion
}

Answer 6

The "Proper" way to do this is to implement IComparable (http://msdn.microsoft.com/en-us/library/system.icomparable.aspx) Interface in your MyCache Class.

This will expose a method called CompareTo which you will have to write in your code.

You would just create that method and put some logic in there that says if this object is greater, less than or equal to the object passed in.

Then you use it in your client code by saying int result = MyCache1.ComparTo(MyCache2);

The result will be -1 0 or 1 based on if its greater than less than or equal too.

Answer 7

What about this:

var MyCache = new SortedDictionary<string, int?>();
MyCache['My result 2'] = (MyCache['My result 2'] ?? 0) + 1;

Answer 8

Do you want something like this.

public class Result {
  public int Hits = 0;
  public string Name = "";

  public void IncreaseHits() {
    this.hits++;
  }

  public Result(String name) {
    this.name = name;
  }
}

class Program {
   public Dictionary<string, Result> MyCache; //what structure to use?


   public main() {
    MyCache.Add("My result 1", new Result("My result 1"));
    MyCache.Add("My result 2", new Result("My result 2"));
    MyCache.Add("My result 3", new Result("My result 3"));

    MyCache["My result 2"].IncreaseHits();
    MyCache["My result 2"].IncreaseHits();
    MyCache["My result 3"].IncreaseHits();

   foreach(Result result in MyCache.Values.OrderByDesc(x => x.Hits)) {
      Console.Write(result.Name + " - hits " + result.Hits);
   }
  }
}

Alternatively

public class MyCacheClass {

   private Dictionary<string,Result> cache = new Dictionary<string, Result>();

   public void IncreaseHits(string name) {
      Result cached;
      if (!cache.TryGetValue(name, out cached)) {
        cached = cache.Add(new Result(name));
      }
      cached.IncreaseHits();
   }

   public string Add(string name) {
      // Need to block duplicates....
      cache.Add(name, new Result(name));
   }

   public IEnumerable<Result> SortDesc {
      get { return cache.Values.OrderByDesc(x => x.Hits); }
   }
}


class Program {
   MyCacheClass MyCache = new MyCacheClass();

   MyCache.Add("result1");
   MyCache.IncreaseHits("My result 2");
   MyCache.IncreaseHits("My result 2");
   MyCache.IncreaseHits("My result 3");

   foreach(Result result in MyCache.SorDesc) {
      Console.WriteLine(string.Format("{0} - hits {1}",result.Name,result.Hits);
   }
}

Answer 9

Why not to use classic List and sort it, using sort method and write your own compare delagate ?

MyCache.Sort(delegate(Result a, Result b)
   {
      if (a.hits > b.hits) return -1;
      if (a.hits < b.hits) return 1;
      return 0;
   });

If you need access by key, you can have 2 structures. One for fast access, second holding sorted data.

Dictionary<String, Result> accessMap;
List<Result> MyCache;
accessMap["Object 1"] = obj1;
MyCache.add(obj1);

accessMap[Object 1].Increase();

//sort MyCache    

foreach(Result result in MyCache) {
  Console.Write(result.Name + " - hits " + result.Hits);
}