我有一个应用程序需要存储一系列电压数据，每个条目就像一对{时间，电压}，
时间不一定是连续的，如果电压不动，我将不会有任何读数。
问题是我还需要一个查找时间戳的函数，例如 getVoltageOfTimestamp(float2second(922.325))
我的解决方案是有一个存储对的双端队列，然后每 30 秒进行一次采样并存储索引进入地图
std::map，
所以在 getVoltageOfTimestamp(float2second(922.325)) 内部，我只需找到距离所需时间最近的interval_of_30_seconds，然后将双端队列指针移动到相应的_index_of_deque，从那里迭代并找到正确的电压。
我不确定这里是否存在更多“计算机科学家”的解决方案，有人能给我线索吗？
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?
发布评论
评论（4）
您可以对
std::deque使用二分搜索，因为时间戳按升序排列。如果您想优化速度，还可以使用
std::map。要查找元素，您可以在地图上使用upper_bound并返回upper_bound找到的元素之前的元素。这种方法使用更多内存（因为std::map有一些开销，并且它还单独分配每个条目）。You could use a binary search on your
std::dequebecause 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 useupper_boundon the map and return the element before the one found byupper_bound. This approach uses more memory (becausestd::map<Timestamp, Voltage>has some overhead and it also allocates each entry separately).您可以直接在双端队列上进行二分搜索来查找最近的时间戳，而不是使用单独的映射。考虑到 std::map 的复杂性要求，进行二分搜索将与映射查找一样高效（两者都是 O(log N)），并且不需要额外的开销。
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.
你介意使用 c++ ox conepts 吗？如果不是
deque> 将完成这项工作。Do you mind using c++ ox conepts ? If not
deque<tuple<Time, Voltage>>will do the job.改进二分搜索的一种方法是识别数据样本。假设您的样本每 30 毫秒一次，然后在向量/列表中存储您获得的读数。在另一个数组中，每 30 秒插入一次数组的索引。现在给定一个时间戳，只需转到第一个数组并找到列表中元素的索引，现在只需转到那里并检查它之前/之后的几个元素。
希望这有帮助。
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.