Find the closest DateTime key in Dictionary<DateTime, double>

Question

I have the Date portion of DateTime as lookup value and like to retrieve the matching value in a Dictionary of type Dictionary<DateTime, double>. Note the DateTime keys are stored as only the Date portion.

My problem is that there may be no key that matches with my lookup value. What I then like to do is to find the nearest previous dateTime.Date key and matching value.

Now, I am aware that Dictionaries are not sorted by key. I could use a SortedDictionary but prefer to use a Dictionary for a specific reason or else switch to a List collection (can be pre-sorted). My question is, what would you recommend to do in this case: Would it be more efficient to retain the Dictionary structure and decrement my lookup value until I find a matching key? Or would it be better to use a list collection and use Linq? Each Dictionary contains around 5000 key/value pairs. Also, please note I look for a highly computationally efficient solution because the frequency of lookups is quite high (potentially many hundred thousand times (each lookup is guaranteed to be different from any previous value)

Answer 1

Since you need it fast, I think the best thing would be to use the results of a BinarySearch. This requires a List<T> that's sorted.

int result = myList.BinarySearch(targetDate);
if (result >= 0)
    return myList[result];
else
{
    int nextLarger = ~result;
    // return next smaller, or if that doesn't exist, the smallest one
    return myList[Math.Max(0, nextLarger - 1)];
}

It should be possible to create a class that combines a Dictionary<TKey,TValue> and a sorted List<TKey> that still serializes like a Dictionary<TKey,TValue>. The serialization might be as simple (in Json.NET) as putting a [JsonConverter(typeof(KeyValuePairConverter))] on your class.

Just for completeness and in case others read this in the future, if speed wasn't very important, you can do it more simply with something like this:

var result = myDict.Keys.Where(x => x < targetDate).Max();

Answer 2

I would use a custom structure and collection to store these informations:

public struct DateValue
{
    public DateValue(DateTime date, double val)
        : this()
    {
        this.Date = date;
        this.Value = val;
    }
    public DateTime Date { get; set; }
}

Here is a possible implementation of a collection that holds all DateValues and encapsulates the logic to return the nearest. It uses List.BinarySearch to find it. If it doesn't find a direct match it uses the logic of BinarySearch to detect the nearest which is:

The index of the specified value in the specified array, if value is found. If value is not found and value is less than one or more elements in array, a negative number which is the bitwise complement of the index of the first element that is larger than value. If value is not found and value is greater than any of the elements in array, a negative number which is the bitwise complement of (the index of the last element plus 1).

public class DateValueCollection : List<DateValue>, IComparer<DateValue>
{
    public DateValueCollection() { }

    public DateValueCollection(IEnumerable<DateValue> dateValues, bool isOrdered)
    {
        if (isOrdered)
            base.AddRange(dateValues);
        else
            base.AddRange(dateValues.OrderBy(dv => dv.Date));
    }

    public DateValue GetNearest(DateTime date)
    {
        if (base.Count == 0)
            return default(DateValue);

        DateValue dv = new DateValue(date, 0);
        int index = base.BinarySearch(dv, this);

        if (index >= 0)
        {
            return base[index];
        }
        // If not found, List.BinarySearch returns the complement of the index
        index = ~index;

        DateValue[] all;
        if(index >= base.Count - 1)
        {
            // proposed index is last, check previous and last
            all = new[] { base[base.Count - 1], base[base.Count - 2] };
        }
        else if(index == 0)
        {
            // proposed index is first, check first and second
            all = new[] { base[index], base[index + 1] };
        }
        else
        {
            // return nearest DateValue from previous and this
            var thisDV = base[index];
            var prevDV = base[index - 1];
            all = new[]{ thisDV, prevDV };
        }
        return all.OrderBy(x => (x.Date - date).Duration()).First();
    }

    public int Compare(DateValue x, DateValue y)
    {
        return x.Date.CompareTo(y.Date);
    }
}

Quick test:

var dateVals = new[] { 
    new DateValue(DateTime.Today.AddDays(10), 1), new DateValue(DateTime.Today, 3), new DateValue(DateTime.Today.AddDays(4), 7) 
};
var dvCollection = new DateValueCollection(dateVals, false);
DateValue nearest = dvCollection.GetNearest(DateTime.Today.AddDays(1));

Answer 3

why worry about optomisation prematurley

do it

THEN AND ONLY THEN if its slow then you have a problem Measure it with a profiler

then understanding starts at which point you try other ways and profile them.

Answer is: If you do it any way at all and there isnt a performance problem you just saved time and managed to do something else useful to add value in your day.

Premature optimization is not only pointless you will usually be completely wrong about where you should be looking.