The algorithm should analyze measured time series data in realtime and should check if all values of the specified last period lay inside a specified range. The range is calculated with max-min over the specified time period.
t | 10:00 | 10:01 | 10:02 | 10:03 | ... | 19:00 | Temp [°C]| 40 | 41.3 | 39 | 43 | | 45 |
- Duration D: Past time to check for min/max
- Max range R: (max-min) < R
e.g: Check if the temperature was steady within 2 °C for the last hour. D=1hour, R=2°C
The algorithm should check periodically during data acquisition if the condition (all values of the last hour have been inside a range of 2°C) is true.
- The sampling time can be from 10Hz to 50kHz.
- The time will always be increasing.
- Since this algorithm should run in an realtime environment there should be no memory allocations during run time
At the moment I have two possible solutions but do not like both of them:
Store all values within the duration in a bounded fifo-buffer and perform a min/max check from start to end periodically. I expect this to be the worst solution
Store the tuples in two B-Trees:
There are two indexes
- TimeIndex t->(t,v): Index from time to tuple,
- ValueIndex v->list(t,v): Index from the value to a list of tuples with this value.
The algorithm will first get all tuples that are outside the time range and remove them in the value index.
Then the value index is updated with the newly measured tuples.
The range can then be determined by looking up the minimum and maximum key in the value index.
I think the second approach is faster but will allocate memory during runtime. Since it should run in a realtime environment I like to avoid allocations.
Is there another possibility with O(log n) and no allocations?