How to store a sequence of timestamped data?

Question

I have an application that need to store a sequence of voltage data, each entry is something like a pair {time, voltage}

the time is not necessarily continuous, if the voltage doesn't move, I will not have any reading.

The problem is that i also need to have a function that lookup timestamp, like, getVoltageOfTimestamp(float2second(922.325))

My solution is to have a deque that stores the paires, then for every 30 seconds, I do a sampling and store the index into a map std::map,

so inside getVoltageOfTimestamp(float2second(922.325)), I simply find the nearest interval_of_30_seconds to the desired time, and then move my pointer of deque to that corresponding_index_of_deque, iterate from there and find the correct voltage.

I am not sure whether there exist a more 'computer scientist' solution here, can anyone give me a clue?

Answer 1

You could use a binary search on your std::deque because the timestamps are in ascending order.

If you want to optimize for speed, you could also use a std::map<Timestamp, Voltage>. For finding an element, you can use upper_bound on the map and return the element before the one found by upper_bound. This approach uses more memory (because std::map<Timestamp, Voltage> has some overhead and it also allocates each entry separately).

Answer 2

Rather then use a separate map, you can do a binary search directly on the deque to find the closet timestamp. Given the complexity requirements of a std::map, doing a binary search will be just as efficient as a map lookup (both are O(log N)) and won't require the extra overhead.

Answer 3

Do you mind using c++ ox conepts ? If not deque<tuple<Time, Voltage>> will do the job.

Answer 4

One way you can improve over binary search is to identify the samples of your data. Assuming your samples are every 30 milliseconds, then in vector/list store the readings as you get them. In the other array, insert the index of the array every 30 seconds. Now given a timestamp, just go to the first array and find the index of the element in the list, now just go there and check few elements preceding/succeeding it.

Hope this helps.