c++ - 如何高效存储时序数据

Question

我有一系列带时间戳的更新，时间戳单调递增

<t1,d1> , <t2,d2> , <t3, d3> .... <tn, dn>

我需要存储这些数据。我事先知道我关心的最大时间增量。所以说我关心的时间增量是 T。所以，我只需要存储所有比 tn 早于 T 个单位的最近更新。

我想按照给我的排序方式存储它们。

总而言之，我正在考虑存储一个排序序列，以便我可以有效地删除较早的元素。类似于 C++ 出队。

关于如何有效地找到我可以删除所有旧条目的截止元素有什么建议吗？

Answer 1

我会使用循环缓冲区。当你要添加一个新的数据点时，检查你要覆盖的值是否是旧的，可​​以删除。如果是，请继续并覆盖。否则，重新分配缓冲区，比方说，两倍大，并将数据指针复制到新缓冲区中。

重新分配和复制可能有点耗时，但总的影响将受到算法基本上摊销常数时间这一事实的限制。

如果确实需要，您可以通过仅将固定数量的元素从旧缓冲区复制到新缓冲区来分散复制。您必须使用每个新数据点移动该数量的元素。只要数字至少为 2，您就会在新缓冲区充满传入数据之前复制所有旧数据。