计算C ++中的移动平均值 [英] Calculating moving average in C++

问题描述

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

我在互联网上找到的大部分资源是计算移动平均的周期信号，

感谢您的支持，窍门是：你可以通过在随机时间获得更新void update（int time，float value）

/ code>。但是，您还需要跟踪更新时间窗口的时间窗口，因此您设置了一个闹钟调用时间+ N

如果实时发生这种情况，您可以请求操作系统进行更新调用时间+ N

$ b调用 void drop_off_oldest_update（int time）
$ b

如果这是一个模拟，你不能从操作系统得到帮助，你需要手动做。在模拟中，你可以用提供的时间作为参数调用方法（这与实时不相关）。然而，一个合理的假设是，保证调用的时间参数增加。在这种情况下，您需要维护一个排序的闹钟时间值列表，并为每个更新和读如果时间参数大于报警列表的头部。虽然更大，您进行报警相关的处理（删除最旧的更新），删除头，然后再次检查，直到处理给定时间之前的所有报警。然后进行更新调用。

到目前为止，我认为很明显你会为实际计算做什么，但我会详细说明。我假设你有一个方法 float read（int time）用于读取值。目标是使这个调用尽可能高效。因此，每次调用读取方法时，不会计算移动平均值。而是预计算上次更新或上一次报警时的值，并通过几个浮点操作调整该值，以考虑自上次更新以来的时间的流逝。 （即除了可能处理堆积报警的列表之外的恒定数目的操作）。

希望这是清楚的 - 这应该是一个非常简单的算法和相当高效

进一步优化：剩余问题之一是如果大量更新在时间窗口内发生，那么会有很长时间其中既没有读取也没有更新，然后读取或更新随之而来。在这种情况下，上述算法在递减地更新正在下降的每个更新的值时将是低效的。这不是必要的，因为我们只关心时间窗口之外的最后更新，所以如果有办法有效地删除所有旧的更新，这将有所帮助。

这样做，我们可以修改算法做一个二进制搜索更新，以找到在时间窗口之前的最近更新。如果需要丢弃的相对较少的更新，则可以递增地更新每个丢弃的更新的值。但是如果有很多更新需要删除，那么在删除旧更新后，可以从头重新计算值。

增量计算的附录： / strong>我应该澄清我的意思是通过上面的增量计算上面的语句tweak这个值通过几个浮点操作来解释自上次更新以来的时间的流逝。初始非增量计算：

以

开头

  sum = 0; 
 updates_in_window = / *窗口内所有更新的集合* /; 
 prior_update'= / *窗口之前的最近更新，时间戳调整到窗口开始* /; 
 relevant_updates = / * union of prior_update'和updates_in_window * /，
  

code> relevant_updates 按照时间增加的顺序：

 每次更新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）操作是以摊销为基础。但请注意上一段中的进一步优化。还要注意在较早的答案中提及的稳定性问题，这意味着浮点错误可能在大量的这种增量操作上累积，使得对于应用而言重要的完整计算的结果存在偏差。 >

I am trying to calculate the moving average of a signal. The signal value ( a double ) is updated at random times. I am looking for an efficient way to calculate it's time weighted average over a time window, in real time. I could do it my self, but it is more challenging than I thought.

Most of the resources I've found over the internet are calculating moving average of periodical signal, but mine updates at random time.

Does anyone know good resources for that ?

Thanks

解决方案

The trick is the following: You get updates at random times via void update(int time, float value). However you also need to also track when an update falls off the time window, so you set an "alarm" which called at time + N which removes the previous update from being ever considered again in the computation.

If this happens in real-time you can request the operating system to make a call to a method void drop_off_oldest_update(int time) to be called at time + N

If this is a simulation, you cannot get help from the operating system and you need to do it manually. In a simulation you would call methods with the time supplied as an argument (which does not correlate with real time). However, a reasonable assumption is that the calls are guaranteed to be such that the time arguments are increasing. In this case you need to maintain a sorted list of alarm time values, and for each update and read call you check if the time argument is greater than the head of the alarm list. While it is greater you do the alarm related processing (drop off the oldest update), remove the head and check again until all alarms prior to the given time are processed. Then do the update call.

I have so far assumed it is obvious what you would do for the actual computation, but I will elaborate just in case. I assume you have a method float read (int time) that you use to read the values. The goal is to make this call as efficient as possible. So you do not compute the moving average every time the read method is called. Instead you precompute the value as of the last update or the last alarm, and "tweak" this value by a couple of floating point operations to account for the passage of time since the last update. (i. e. a constant number of operations except for perhaps processing a list of piled up alarms).

Hopefully this is clear -- this should be a quite simple algorithm and quite efficient.

Further optimization: one of the remaining problems is if a large number of updates happen within the time window, then there is a long time for which there are neither reads nor updates, and then a read or update comes along. In this case, the above algorithm will be inefficient in incrementally updating the value for each of the updates that is falling off. This is not necessary because we only care about the last update beyond the time window so if there is a way to efficiently drop off all older updates, it would help.

To do this, we can modify the algorithm to do a binary search of updates to find the most recent update before the time window. If there are relatively few updates that needs to be "dropped" then one can incrementally update the value for each dropped update. But if there are many updates that need to be dropped then one can recompute the value from scratch after dropping off the old updates.

Appendix on Incremental Computation: I should clarify what I mean by incremental computation above in the sentence "tweak" this value by a couple of floating point operations to account for the passage of time since the last update. Initial non-incremental computation:

start with

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 */,  

then iterate over relevant_updates in order of increasing time:

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

and finally

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

Now if exactly one update falls off the window but no new updates arrive, adjust sum as:

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

(note it is prior_update' which has its timestamp modified to start of last window beginning). And if exactly one update enters the window but no new updates fall off, adjust sum as:

sum += previously_most_recent_update.value * corresponding_time_to_next_update. 

As should be obvious, this is a rough sketch but hopefully it shows how you can maintain the average such that it is O(1) operations per update on an amortized basis. But note further optimization in previous paragraph. Also note stability issues alluded to in an older answer, which means that floating point errors may accumulate over a large number of such incremental operations such that there is a divergence from the result of the full computation that is significant to the application.

这篇关于计算C ++中的移动平均值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！