What algo/design pattern do i need to keep limited time series data constantly updated?

Question

I'm a hobbyist coder; never worked professionally. I am not looking for anyone to write code for me, but I need to know how to approach this problem and, perhaps, ideas for further research. This problem is an outgrowth of my kid's science project that I wanted to toy with.

Bottom line is: I have a sensor that feeds data objects at irregular and unpredictable intervals (temp, air pressure, other things). Each new "update" feeds another data object with all the pertinent info...and each object has a time stamp. The unpredictability is the core of the problem, and that will not change. As my code gathers new data objects at irregular intervals, I need to run simple arithmetic operations on the data objects for the last n minutes. I need to output these arithmetic operations continuously on each new "update" of fresh data. The sensor could put out as many as, say, 20 updates per second...or fewer. CPU and RAM usage are a mild concern, but I want to focus on getting working design first.

At first, I was thinking circular array or queue, but that's no good since I do not know how many objects will cover the last n minutes.

Next, I considered a doubly linked list. The problem with this approach is that it will have to consume heavy CPU by iterating over the entire list each new "update" in order to remove outdated objects from the list or will have to consume a lot of ram if I do not remove old objects from the list each time.

I am wondering what design patterns (and data structures) might fit this problem, and what other items I could research to learn more to solve this problem.

I realize I am not giving much information here, but I want to keep simple and I believe I have given the gist of the problem.

I really appreciate any help. Btw, I'm using C# and the CLR for now. Python might be a better option since this is data-science'ish. I believe I could write and/or consume a Python library/class. I'm not real fluent with Python.

---

UPDATE - 8/30

I've been thinking in response to everyone's responses--which are great and I really appreciate.

I'm thinking, use the ConcurrentQueue class from the .NET library as my core data structure. I did not know it was re-sizable until @amon mentioned it. A queue seems perfect because I can iterate from the head of the queue and peek at the next timestamp, using a while loop (i.e., while the next "peek" is outside the n-minute time window then dequeue). Since all of the data objects must necessarily be enqueue'd in temporal order, this should work with the head always being the oldest and tail always being the newest data object. This mitigates my concern about CPU usage in keeping the queue "current" (i.e., only containing data objects inside the n-minute time window).

As to updating the user's view and mitigating CPU usage there, I could update the view every x seconds as mentioned by @JohnWu. I would probably use a Thread Timer which would update the data objects underlying the user's view on a separate thread at a fixed interval.

If this uses too much CPU, I will investigate saving pieces of state as discussed by @ErikEidt. But since I'm not calculating only averages, that will get a little complicated. I hoping the above deals with any resource problems.

Just wanted to say thanks for the insight.

Next step is to learn more about threading.

Answer 1

Things to think about:

Don't automatically assume that a doubly linked list of 20 items per second over 60 minutes (e.g. 20x60x60 = 72,000) will necessarily tax your CPU unless you've tried it.

---

Certain algorithms might work nicely for you. For example, if you are computing an average, you only need subtract/undo the values that have aged out, and factor in/account for the ones that are new. You don't always have to iterate over the whole list of values in the current time window.

So, let's say you want to compute the avg temp over time, and you're using a linked list of timestamp'ed values.

Beyond the list itself, maintain two pieces of state for the running average, both initially zero, one for sum and one for count.

On new data arriving, you add an element to the end of the list, while also adjusting the sum to accumulate the new temp value, and incrementing the count.

You then age out old values by traversing from the beginning (old) end of the list stopping this when you reach an entry that shouldn't be aged out yet. For each element that has aged out, remove it from the list and subtract its temp value from the sum and decrement the count. (For extra speed and complexity, you might hold off removing each individual aged element and fix the head of list only once, after you find the new beginning.)

The computation is largely complete now, and the average is the sum divided by the count. Output that to the next object down the line, and wait for more updates.

The net result is that as new data arrives, you are only handling that new data, and any old things to age out, but not the rest of the list, which is perhaps the bulk of the list.

---

You might find that buffering the computation is appropriate, for example, when you get new data, schedule an update for a tenth of a second from now. Then any values received in the mean time could all be processed all together.

---

If you are worried about garbage collection for the list, move the aged out/removed entries to a separate free list, and preferentially reuse those first rather than allocating new elements to hold updates.

Answer 2

One possible approach, in just about any language that supports them, it to use a double ended queue. The required methods are left and right push and pop plus in place access, although if in place access is not possible there is a work around.

My approach would be:

1. Each time a new reading arrived push it, with the time data on to one end of the queue and calculate the oldest time stamp that is now valid, (i.e. New time stamp minus 300 seconds).
2. Pop values from the other end of the queue until the time stamp is greater than or equal to the threshold. Push that last value back onto the same end it came from.
3. Call your summary generation code on the queue - this is where in place access is handy otherwise you will need to roll the queue through i.e. record the time stamp at one end by popping, add the value into the summary and push it to the other end then repeat until you get back to that one.

If your data arrival rate is potentially faster than your code for the above you may have to have an incoming queue where values are held until added in as a block.