How to get max sum range for specific time period from values in Dictionary

Question

If there is a sequence of numbers with datetime in Dictionary like below, what is the most efficient way to select the max sum range of the specific time period programmatically? The below is just an example but the actual data I have has more than 10,000 entries in a dictionary.

12/31/2013 10:00:01  96
12/31/2013 10:00:02  20
12/31/2013 10:00:03  51
12/31/2013 10:00:04  62
12/31/2013 10:00:05  84
12/31/2013 10:00:06  78
12/31/2013 10:00:07  74
12/31/2013 10:00:08 150
12/31/2013 10:00:09 130
12/31/2013 10:00:10  99
12/31/2013 10:00:11 101
12/31/2013 10:00:12 123
12/31/2013 10:00:13  51
12/31/2013 10:00:14  61
12/31/2013 10:00:15  19
12/31/2013 10:00:16  81
12/31/2013 10:00:17  98
12/31/2013 10:00:18  39
12/31/2013 10:00:19  45
12/31/2013 10:00:20  65

For example, the max sum range for 5 seconds is between 10:00:08 and 10:00:12. Obviously, there are a couple of ways to get this range, but I am looking for most efficient way to do this in C#. Could you please share your ideas and techniques to do this (maybe with Linq but not necessary)? Thank you for your help in advance.

Answer 1

LINQ is not going to help you if you are looking for efficiency.

Brute-force algorithm out of my head:

1. Convert the dictionary to list of time/value
2. Sort the list by time
3. Use sort of "moving window" technique where you add values of new entries and remove values of old entries. The size of the window depends on the range you specified.
4. For each window, you get the sum of that window so look for maximal window.

Source here (I borrowed parsing code from StriplingWarrior):

    public struct TimeValue
    {
        public DateTime time {get;set;}
        public int value{get;set;}
    }

    static void Main(string[] args)
    {
        var txt = @"12/31/2013 10:00:01  96
        12/31/2013 10:00:02  20
        12/31/2013 10:00:03  51
        12/31/2013 10:00:04  62
        12/31/2013 10:00:05  84
        12/31/2013 10:00:06  78
        12/31/2013 10:00:07  74
        12/31/2013 10:00:08 150
        12/31/2013 10:00:09 130
        12/31/2013 10:00:10  99
        12/31/2013 10:00:11 101
        12/31/2013 10:00:12 123
        12/31/2013 10:00:13  51
        12/31/2013 10:00:14  61
        12/31/2013 10:00:15  19
        12/31/2013 10:00:16  81
        12/31/2013 10:00:17  98
        12/31/2013 10:00:18  39
        12/31/2013 10:00:19  45
        12/31/2013 10:00:20  65";

        var values = 
            (from line in txt.Split(new[]{Environment.NewLine}, StringSplitOptions.RemoveEmptyEntries)
            let pair = line.Split(new[]{' '}, 3, StringSplitOptions.RemoveEmptyEntries)
            select new TimeValue
            {
                time = DateTime.ParseExact(pair[0] + " " + pair[1], "MM/dd/yyyy HH:mm:ss", CultureInfo.InvariantCulture),
                value = int.Parse(pair[2])
            })
            .OrderBy(e => e.time)
            .ToArray();;

        TimeSpan range = TimeSpan.FromSeconds(5);

        int totalMax = -1;
        int maxTail = -1;
        int maxHead = -1;

        int tail = 0; // index at tail of the window
        int currentMax = 0;
        for (int head = 0; head < values.Length; head++) // head of the window
        {
            currentMax += values[head].value; // add next value
            DateTime tailTime = values[head].time - range;
            while (values[tail].time <= tailTime) // remove values at tail that don't fit in range
            {
                currentMax -= values[tail].value;
                tail++;
            }

            if (currentMax > totalMax)
            {
                totalMax = currentMax;
                maxTail = tail;
                maxHead = head;
            }
        }

        Console.WriteLine("Maximum range from times:" + values[maxTail].time + " - " + values[maxHead].time);
    }

Answer 2

This code appears to work in LINQPad. It follows the pattern @Euphoric suggested.

void Main()
{
    var txt = @"12/31/2013 10:00:01  96
    12/31/2013 10:00:02  20
    12/31/2013 10:00:03  51
    12/31/2013 10:00:04  62
    12/31/2013 10:00:05  84
    12/31/2013 10:00:06  78
    12/31/2013 10:00:07  74
    12/31/2013 10:00:08 150
    12/31/2013 10:00:09 130
    12/31/2013 10:00:10  99
    12/31/2013 10:00:11 101
    12/31/2013 10:00:12 123
    12/31/2013 10:00:13  51
    12/31/2013 10:00:14  61
    12/31/2013 10:00:15  19
    12/31/2013 10:00:16  81
    12/31/2013 10:00:17  98
    12/31/2013 10:00:18  39
    12/31/2013 10:00:19  45
    12/31/2013 10:00:20  65";
    var data = 
        (from line in txt.Split(new[]{Environment.NewLine}, StringSplitOptions.RemoveEmptyEntries)
        let pair = line.Split(new[]{' '}, 3, StringSplitOptions.RemoveEmptyEntries)
        select new Entry
        {
            dt = DateTime.Parse(pair[0] + " " + pair[1]),
            val = int.Parse(pair[2])
        })
        .OrderBy(e => e.dt);

    var range = TimeSpan.FromSeconds(5);
    var queue = new Queue<Entry>();
    int max = 0;
    DateTime? maxStart = null;
    DateTime? maxEnd = null;
    int sum = 0;

    foreach (var entry in data)
    {
        queue.Enqueue(entry);
        sum += entry.val;
        while(queue.Count > 0 && entry.dt - queue.Peek().dt >= range)
        {
            sum -= queue.Dequeue().val;
        }
        if(sum > max)
        {
            max = sum;
            maxStart = queue.Peek().dt;
            maxEnd = entry.dt;
        }
    }
    Console.WriteLine("Max is {0}, between {1} and {2}", max, maxStart, maxEnd);
}

public class Entry
{
    public DateTime dt;
    public int val;
}