I need a sorted Dictionary, but I would like to limit its capacity

Question

I have a Dictionary<..., Statistics>, where Statistics is a custom structure with some fields. This struct implements the IComparer interface.

public struct Statistics : IComparer<Statistics>
{
    public UInt64 NumberOfOccurrences;
    public UInt64 TotalNumberOfWords;
    ...

    public int Compare(Statistics x, Statistics y)
    {
        // code for compare the statistics
        ...
    }
}

I chose the dictionary to have better performance during updates of existing statistics. However, I also want good performance in reading statistics in order from best to worst, so I should use a SortedDictionary in place of Dictionary.

Now I would like to limit the number of entries within the dictionary to a specified value, by removing the entries with worst statistics, in order to limit the memory usage. I have seen that SortedDictionary does not have constructors with a capacity argument, so I thought I'd store the maximum number of entries in the integer variable elementsCountLimit. Before adding a new entry in the SortedDictionary, I could perform the following check:

if (dict.Count == elementsCountLimit)
{
    // Remove the last entry, that is the
    // entry with worst statistics.
}

1. But, If I don't know the key, how can I remove the last entry?
2. How can I limit the memory usage?

Answer 1

if you don't mind iterating over the keys dict.Remove(dict.Keys.Last());

Answer 2

You could use binary search to handle this. Using something like:

// example variables for clarity of them in the method
private List<Statistics> _statistics;
private int _capacity;

public void AddStatistic(Statistics statistic)
{
    var index = _statistics.BinarySearch(statistic);

    // if it's not in the list, index will the negative representation
    // of where it should be if sorted.
    if(index < 0)
    {
       index = ~index;
    }

   // insert it into the correct location
    _statistics.Insert(index, statistic);

    if(_statistics.Length > capacity)
    {
        // assuming sorted best to worst, remove the last item
        _statistics.RemoveAt(_statistics.Count - 1);
    }
}

Answer 3

Write a simple array implementation for Heap<T>. Then, use a Heap<TKey>, and a Dictionary<TKey, Statistics> together. Heap will serve as a priority queue. Careful: The top element of the heap should be the item to be deleted next. i.e. If you want to keep the "maximum" items, the heap should keep the minimum item at the root. When you will insert an item and the heap is full, also delete the root in Log(n) time. Whenever you delete an item from the heap delete it from the dictionary as well. Pseudocode:

Insert (TKey item, Heap<TKey> heap, Dictionary<TKey, TStatistics> dictionary)
    insert (item, heap)
    if heap capacity is exceeded:
        var deleteditem = deletemin(heap)
        if(deleteditem!=item):
            insert(item, dictionary)
            delete(deleteditem,dictionary)
    else:
        insert(item,dictionary)

Answer 4

A SortedDictionary is sorted by its keys and not the values. So if you want to remove entries based on some properties of the values you need to iterate over all entries and determine which one to remove. This makes it an O(n) operation which negates the performance benefits of the dictionary.

I would use a custom data structure to keep the data in a way you want and encapsulate any functionality of a maximum number of entries:

public class StatisticsMap<TKey>
{
    public StatisticsMap<TKey>(int maxEntries)
    {
         _MaxEntries = maxEntries;
    }

    private int _MaxEntries;
    private SortedList<Tuple<Statistics, TKey>> _SortedStatistics;
    private Dictionary<TKey, Statistics> _KeyedStatistics;

    public void Add(TKey key, Statistics stat)
    {
        _SortedStatistics.Add(Tuple.Create(stat, key));
        _KeyedStatistics[key] = stat;
        while (_SortedStats.Count > _MaxEntries)
        {
             int lastIndex = _SortedStatistics.Count - 1;
             var doomed = _SortedStatistics[lastIndex];
             _SortedStatistics.RemoveAt(lastIndex);
             _KeyedStatistics.Remove(doomed.Item2);
        }
    }

    public Statistics Get(TKey key)
    {
        return _KeyedStatistics[key];
    }
}

Depending on how you intend to use it you could implement the IDictionary interface for greater flexibility.

TradeOff: Uses double the memory.

Edit

You only need a dictionary if you need O(1) access to the Statistics objects by a given key. If you can get away with an index or if iterating over the list is good enough then you don't need a dictionary. A SortedList and a SortedDictionary do not have any built in capacity limits - none of the Framework data structures do (except an array which has a fixed size). You need to add that part yourself no matter what you use.

The code I suggested assumes that you need O(1) access to a Statistics object by a given key and that you need to remove Statistics object based on certain properties effectively.