时间滑动窗口 - 数据结构和垃圾回收

Question

9

我正在尝试实现类似于移动平均的东西。

在此系统中，每个时间段内没有整数数量的保证。我确实需要为每个时间段计算平均值。因此，我不能只按整数数量滑动列表，因为这不会相对于时间。

我可以记录每个值及其关联时间的记录。我们将通过系统运行大量数据，因此“垃圾回收”旧数据非常重要。

还需要注意的是，我需要在每个时间段结束后将平均值保存到磁盘上。但是，在将数据保存到磁盘并引入新周期的数据之间可能存在一些重叠。

有哪些有效的数据结构可用于存储、滑动和垃圾回收这种类型的数据？

- Kurtis

我提供了一个答案，实际上只是关于你真正需求的猜测。如果我猜错了，请告诉我，我会删除它。 - rici

1

让我想起了这个问题（将答案应用到这个问题上应该相当简单）。 - Bernhard Barker

@rici - 实际上，你说得很对。感谢你“读懂了字里行间”！ - Kurtis

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rici · Accepted Answer

问题描述和问题本身矛盾：所描述的不是移动平均数，因为每个时间段的平均数都是不同的。（“我需要计算每个时间段的平均数。”）因此这可以采用一个极其简单的方法解决：

对于每个时间段，维护观察值的数量和总和。

在时间段结束时，计算平均值。

我猜想实际所需的是这样的：每隔一秒钟（计算周期），我想要知道在过去一分钟内（聚合周期）的平均观测值。

这可以通过循环桶数组轻松解决，每个桶代表一个计算期间的值。将有aggregation period / computation period 这么多桶。每个桶包含一个计数和总和。还要维护一个当前总/总和以及一个累计总和/计数。将每个观测值添加到当前总/总和中。

在每个计算周期结束时：

1. 从累计总数/计数中减去第一个（循环）周期的总数/计数 2. 将当前总数/计数加入累计总数/计数 3. 基于累计总数/计数报告平均值 4. 使用当前总数/计数替换第一个周期的值 5. 清除当前总数/计数 6. 推进循环缓冲区的原点。

如果你确实需要在任何时候计算先前观测值在某个给定周期内的平均数，那么你就需要一个更复杂的数据结构，即可扩展的循环缓冲区。但是这样精确的计算实际上很少有必要进行，而基于桶的近似算法通常足以满足数据目的，并且对于内存管理来说长期来看更可持续，因为其内存需求从一开始就被固定了。