4

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.

  • 2
    Is there some reason you're writing all of this from scratch when you could be dumping the data into a database and letting it do the heavy lifting? – Blrfl Aug 29 '17 at 1:34
  • 1
    Who is reading the output-- a machine or a person? If a person, why would they need an update as many as 20 times per second? – John Wu Aug 29 '17 at 2:40
  • please don't cross-post: stackoverflow.com/questions/45928084/… "Cross-posting is frowned upon as it leads to fragmented answers splattered all over the network..." – gnat Aug 29 '17 at 8:57
  • John Wu, you're right. I could update the user's view each second or every two seconds and be fine...and save resources Thank you for challenging what I was thinking. Like I said, I'm not a pro. – LeeRoy Aug 30 '17 at 0:54
  • 1
    The very short summary would be that you put your measurements into the database and write queries to ask it questions and do maintenance like pruning old data. You still have to specify what you want in the queries (e.g., SELECT AVG(pressure) WHERE <condition>), but the database organizes the data and you're not stuck having to write new code when your questions change. SQLite is more than capable enough for an application like yours and gives you the option of running in memory if you don't care about persistence or on disk if you do. – Blrfl Aug 30 '17 at 14:38
5

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.

  • 1
    The second phase to age out old values could be performed once OP performs the average since you're already reading each item and checking that it is within the minute timeframe. Once OP finds one that isn't, assuming they are in order of assertion, OP can just drop off the rest, with no further calculation necessary. For that matter, assuming memory isn't an issue, extra items can be dropped only upon calculation, further optimizing the calculation. I agree with you that a linked list would be best for flexibility, though I think a singly linked list is sufficient. – Neil Aug 29 '17 at 12:45
  • Does the algorithm you're describing have a name? – ClemC Aug 29 '17 at 15:55
  • +1. But instead of trying to outsmart the GC with respect to doubly linked lists, one could simply use an ordinary resizeable queue data structure like System.Collections.Generic.Queue in .NET or implement this wonderful data structure yourself. – amon Aug 29 '17 at 17:12
  • @Neil, thanks for calling out the sufficiency of singly linked list here. – Erik Eidt Aug 29 '17 at 17:48
  • @ClemC, not sure, perhaps an adaptation "greedy", where iteration is distributed over time? From interviewcake.com: ""A greedy algorithm iterates through the problem space taking the optimal solution "so far," until it reaches the end. The greedy approach is only optimal if the problem has "optimal substructure," which means stitching together optimal solutions to subproblems yields an optimal solution."" The subproblems stich together here by addition/subtraction. – Erik Eidt Aug 29 '17 at 17:53
1

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.

  • 2
    OP's already cycling through for calculating average and whatnot, so OP will know if an expired item has been hit, and can then drop the rest from the list at that point, with little more than a singly linked list and one pass. – Neil Aug 29 '17 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.