c++ - 在 C++ 中计算移动平均线

Question

我正在尝试计算信号的移动平均值。信号值 ( a double ) 随机更新。
我正在寻找一种有效的方法来实时计算时间窗口内的时间加权平均值。我可以自己做，但它比我想象的更具挑战性。

我在互联网上找到的大部分资源都在计算周期性信号的移动平均值，但我的更新是随机时间的。

有没有人知道好的资源？

谢谢

Answer 1

技巧如下:您可以通过 void update(int time, float value) 随机获取更新。 .但是，您还需要跟踪更新何时超出时间窗口，因此您设置了一个“警报”，该警报在 time + N 处调用。这将在计算中不再考虑先前的更新。

如果这是实时发生的，您可以请求操作系统调用方法 void drop_off_oldest_update(int time)调用 time + N
如果这是模拟，则无法从操作系统获得帮助，需要手动进行。在模拟中，您将使用作为参数提供的时间(与实时无关)调用方法。然而，一个合理的假设是保证调用的时间参数在增加。在这种情况下，您需要维护警报时间值的排序列表，并且对于每个 update和 read调用您检查时间参数是否大于警报列表的头部。虽然您最好进行与警报相关的处理(删除最旧的更新)，但请移开头部并再次检查，直到处理完给定时间之前的所有警报。然后进行更新调用。

到目前为止，我已经假设你会为实际计算做些什么是显而易见的，但我会详细说明以防万一。我假设你有一个方法 float read (int time)用于读取值。目标是使此调用尽可能高效。因此，您不必每次都计算 read 的移动平均线。方法被调用。相反，您预先计算上次更新或上次警报的值，并通过几个浮点运算“调整”该值，以说明自上次更新以来的时间流逝。 (即除了可能处理堆积的警报列表之外的恒定数量的操作)。

希望这很清楚——这应该是一个非常简单的算法并且非常有效。

进一步优化 : 剩下的问题之一是如果在时间窗口内发生大量更新，那么很长一段时间既没有读取也没有更新，然后出现读取或更新。在这种情况下，上述算法在为每个正在下降的更新增量更新值方面效率低下。这不是必需的，因为我们只关心时间窗口之外的最后一次更新，所以如果有一种方法可以有效地删除所有较旧的更新，它会有所帮助。

为此，我们可以修改算法以对更新进行二分搜索，以找到时间窗口之前的最新更新。如果需要“删除”的更新相对较少，则可以为每个删除的更新增量更新值。但是，如果需要删除许多更新，则可以在删除旧更新后从头开始重新计算该值。

增量计算附录:我应该在上面的句子“调整”这个值中通过几个浮点运算澄清我所说的增量计算的意思，以说明自上次更新以来的时间流逝。初始非增量计算:

从...开始

sum = 0; 
updates_in_window = /* set of all updates within window */; 
prior_update' = /* most recent update prior to window with timestamp tweaked to window beginning */; 
relevant_updates = /* union of prior_update' and updates_in_window */,  

然后迭代 relevant_updates按时间增加的顺序:

for each update EXCEPT last { 
    sum += update.value * time_to_next_update; 
},  

最后
moving_average = (sum + last_update * time_since_last_update) / window_length; .

现在，如果正好有一个更新掉出窗口但没有新的更新到达，请调整 sum作为:

sum -= prior_update'.value * time_to_next_update + first_update_in_last_window.value * time_from_first_update_to_new_window_beginning;

(注意它是 prior_update'，它的时间戳被修改为最后一个窗口开始的开始)。如果只有一个更新进入窗口但没有新的更新掉下来，调整sum作为:

sum += previously_most_recent_update.value * corresponding_time_to_next_update. 

很明显，这是一个粗略的草图，但希望它展示了如何保持平均值，以便在摊销的基础上每次更新是 O(1) 操作。但请注意上一段中的进一步优化。还要注意旧答案中提到的稳定性问题，这意味着浮点错误可能会在大量此类增量操作中累积，从而与对应用程序很重要的完整计算的结果存在分歧。