Clean up algorithm

I've made an C# application which connects to my webcam and reads the images开发者_运维技巧 at the speed the webcam delivers them. I'm parsing the stream, in a way that I have a few jpeg's per seconds.

I don't want to write all the webcam data to the disk, I want to store images in memory. Also the application will act as a webserver which I can supply a datetime in the querystring. And the webserver must server the image closest to that time which it still has in memory.

In my code I have this:

Dictionary<DateTime, byte[]> cameraImages;

of which DateTime is the timestamp of the received image and the bytearray is the jpeg. All of that works; also handling the webrequest works. Basically I want to clean up that dictionary by keep images according to their age.

Now I need an algorithm for it, in that it cleans up older images.

I can't really figure out an algorithm for it, one reason for it is that the datetimes aren't exactly on a specific moment, and I can't be sure that an image always arrives. (Sometimes the image stream is aborted for several minutes). But what I want to do is:

• Keep all images for the first minute.
• Keep 2 images per second for the first half hour.
• Keep only one image per second if it's older than 30 minutes.
• Keep only one image per 30 seconds if it's older than 2 hours.
• Keep only one image per minute if it's older than 12 hours.
• Keep only one image per hour if it's older than 24 hours.
• Keep only one image per day if it's older than two days.
• Remove all images older than 1 weeks.

The above intervals are just an example.

Any suggestions?

---

I think @Kevin Holditch's approach is perfectly reasonable and has the advantage that it would be easy to get the code right.

If there were a large number of images, or you otherwise wanted to think about how to do this "efficiently", I would propose a thought process like the following:

Create 7 queues, representing your seven categories. We take care to keep the images in this queue in sorted time order. The queue data structure is able to efficiently insert at its front and remove from its back. .NET's Queue would be perfect for this.

Each Queue (call it Qi) has an "incoming" set and an "outgoing" set. The incoming set for Queue 0 is those images from the camera, and for any other set it is equal to the outgoing set for Queue i-1

Each queue has rules on both its input and output side which determine whether the queue will admit new items from its incoming set and whether it should eject items from its back into its outgoing set. As a specific example, if Q3 is the queue "Keep only one image per 30 seconds if it's older than 2 hours", then Q3 iterates over its incoming set (which is the outcoming set of Q2) and only admits item i where i's timestamp is 30 seconds or more away from Q3.first() (For this to work correctly the items need to be processed from highest to lowest timestamp). On the output side, we eject from Q3's tail any object older than 12 hours and this becomes the input set for Q4.

Again, @Kevin Holditch's approach has the virtue of simplicity and is probably what you should do. I just thought you might find the above to be food for thought.

---

You could do this quite easily (although it may not be the most efficient way by using Linq).

E.g.

var firstMinImages = cameraImages.Where(
    c => c.Key >= DateTime.Now.AddMinutes(-1));

Then do an equivalent query for every time interval. Combine them into one store of images and overwrite your existing store (presuming you dont want to keep them). This will work with your current criteria as the images needed get progressively less over time.

---

My strategy would be to Group the elements into buckets that you plan to weed out, then pick 1 element from the list to keep... I have made an example of how to do this using a List of DateTimes and Ints but Pics would work exactly the same way.

My Class used to store each Pic

    class Pic
    {
        public DateTime when {get;set;}
        public int val {get;set;}
    }

and a sample of a few items in the list...

        List<Pic> intTime = new List<Pic>();
        intTime.Add(new Pic() { when = DateTime.Now, val = 0 });
        intTime.Add(new Pic() { when = DateTime.Now.AddDays(-1), val = 1 });
        intTime.Add(new Pic() { when = DateTime.Now.AddDays(-1.01), val = 2 });
        intTime.Add(new Pic() { when = DateTime.Now.AddDays(-1.02), val = 3 });
        intTime.Add(new Pic() { when = DateTime.Now.AddDays(-2), val = 4 });
        intTime.Add(new Pic() { when = DateTime.Now.AddDays(-2.1), val = 5 });
        intTime.Add(new Pic() { when = DateTime.Now.AddDays(-2.2), val = 6 });
        intTime.Add(new Pic() { when = DateTime.Now.AddDays(-3), val = 7 });

Now I create a helper function to bucket and remove...

    private static void KeepOnlyOneFor(List<Pic> intTime, Func<Pic, int> Grouping, DateTime ApplyBefore)
    {
        var groups = intTime.Where(a => a.when < ApplyBefore).OrderBy(a=>a.when).GroupBy(Grouping);
       foreach (var r in groups)
       {
           var s = r.Where(a=> a != r.LastOrDefault());
           intTime.RemoveAll(a => s.Contains(a));
       }
    }

What this does is lets you specify how to group the object and set an age threshold on the grouping. Now finally to use...

This will remove all but 1 picture per Day for any pics greater than 2 days old:

        KeepOnlyOneFor(intTime, a => a.when.Day, DateTime.Now.AddDays(-2));

This will remove all but 1 picture for each Hour after 1 day old:

        KeepOnlyOneFor(intTime, a => a.when.Hour, DateTime.Now.AddDays(-1));

---

If you are on .net 4 you could use a MemoryCache for each interval with CachItemPolicy objects to expire them when you want them to expire and UpdateCallbacks to move some to the next interval.