在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）每次更新的操作按摊销基准进行。但请注意前一段中的进一步优化。还要注意较老答案中提到的稳定性问题，这意味着浮点错误可能会累积在大量这样的增量操作上，从而导致对应用程序有重大意义的完整计算结果出现分歧。

Answer 2

注：显然，这是不解决这个的方式。留在这里以便参考这种方法的错误。检查评论。

更新 - 基于奥利的评论...不确定他谈论的不稳定。

使用针对值的“抵达时间”的排序地图。值到达时，将排序图的到达时间与其值一起添加并更新移动平均值。

警告这是伪代码：

SortedMapType< int, double > timeValueMap; 

void onArrival(double value) 
{ 
    timeValueMap.insert((int)time(NULL), value); 
} 

//for example this runs every 10 seconds and the moving window is 120 seconds long 
void recalcRunningAverage() 
{ 
    // you know that the oldest thing in the list is 
    // going to be 129.9999 seconds old 
    int expireTime = (int)time(NULL) - 120; 
    int removeFromTotal = 0; 
    MapIterType i; 
    for(i = timeValueMap.begin(); 
    (i->first < expireTime || i != end) ; ++i) 
    { 
    } 

    // NOW REMOVE PAIRS TO LEFT OF i 

    // Below needs to apply your time-weighting to the remaining values 
    runningTotal = calculateRunningTotal(timeValueMap); 
    average = runningTotal/timeValueMap.size(); 
} 

有...不完全充实，但你的想法。

注意事项： 正如我所说的上述是伪代码。你需要选择一个合适的地图。 迭代时不要删除对，因为您将使迭代器失效，并且必须重新开始。
另请参阅下面的Oli的评论。

Answer 3

如果近似值正确，且样本之间有最短时间，则可尝试超级采样。有一个表示均匀间隔的时间间隔小于最小值的数组，并且在每个时间段存储接收到的最新采样。间隔越短，平均值越接近真实值。该期限不得大于最小值的一半，否则有可能错过样本。

Answer 4

#include <map> 
#include <iostream> 

// Sample - the type of a single sample 
// Date - the type of a time notation 
// DateDiff - the type of difference of two Dates  
template <class Sample, class Date, class DateDiff = Date> 
class TWMA { 
private: 
    typedef std::map<Date, Sample> qType; 
    const DateDiff windowSize; // The time width of the sampling window 
    qType samples; // A set of sample/date pairs 
    Sample average; // The answer 

public: 

    // windowSize - The time width of the sampling window 
    TWMA(const DateDiff& windowSize) : windowSize(windowSize), average(0) {} 

    // Call this each time you receive a sample 
    void 
    Update(const Sample& sample, const Date& now) { 
    // First throw away all old data 
    Date then(now - windowSize); 
    samples.erase(samples.begin(), samples.upper_bound(then)); 

    // Next add new data 
    samples[now] = sample; 

    // Compute average: note: this could move to Average(), depending upon 
    // precise user requirements. 
    Sample sum = Sample(); 
    for(typename qType::iterator it = samples.begin(); 
     it != samples.end(); 
     ++it) { 
     DateDiff duration(it->first - then); 
     sum += duration * it->second; 
     then = it->first; 
    } 
    average = sum/windowSize; 
    } 

    // Call this when you need the answer. 
    const Sample& Average() { return average; } 

}; 

int main() { 
    TWMA<double, int> samples(10); 

    samples.Update(1, 1); 
    std::cout << samples.Average() << "\n"; // 1 
    samples.Update(1, 2); 
    std::cout << samples.Average() << "\n"; // 1 
    samples.Update(1, 3); 
    std::cout << samples.Average() << "\n"; // 1 
    samples.Update(10, 20); 
    std::cout << samples.Average() << "\n"; // 10 
    samples.Update(0, 25); 
    std::cout << samples.Average() << "\n"; // 5 
    samples.Update(0, 30); 
    std::cout << samples.Average() << "\n"; // 0 
}