用C++计算移动平均值

Question

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

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

有谁知道这方面的好资源？

谢谢

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)操作.但请注意前一段中的进一步优化.还要注意在较旧的答案中提到的稳定性问题,这意味着浮点错误可能在大量此类增量操作中累积,使得与完全计算的结果存在差异,这对应用程序而言是重要的.