在C++中计算移动平均值

Question

我正在尝试计算信号的移动平均值。该信号值（一个double类型）在随机时间更新。我正在寻找一种有效的方法，在实时情况下计算出其时间加权平均值，我可以自己完成，但这比我想象的更具挑战性。

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

请问是否有好的资源可供参考？

谢谢

- 0x26res

---

你目前有什么进展？你怎么知道它效率低下？ - Oliver Charlesworth

在您的情境中，这可能有用，也可能没有用。指数移动平均线可能是一个适合固定窗口替代方案的选择。它可以很容易地进行递归计算。 - NPE

如果您的数据类型是整数，计算固定窗口移动平均值也非常便宜（O（1））。 - Oliver Charlesworth

由于权重函数未知（不同的时间间隔），因此您将无法在不保留最后N个值并每次计算加权平均值的情况下即时计算移动平均值。 - INS

与指数移动平均相关：https://dev59.com/YXNA5IYBdhLWcg3wSrua - edA-qa mort-ora-y

Answer 1

技巧如下：您会随机时间通过 void update(int time, float value) 获得更新。但是，您还需要追踪何时更新在时间窗口之外，因此您设置了一个“警报”，该警报在 time + N 处被调用，从而从计算中删除了以前的更新。

如果这是实时发生的，您可以请求操作系统在 time + N 时调用一个方法 void drop_off_oldest_update(int time)。

如果这是模拟，则无法从操作系统获得帮助，并且您需要手动执行。在模拟中，您将调用带有提供时间参数的方法（该参数与实际时间不相关）。但是，合理的假设是调用保证时间参数正在增加。在这种情况下，您需要维护已排序的警报时间值列表，并对每个 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; 
},  

最后，

移动平均值 = (总和 + 上次更新的数据 * 距离上次更新时间) / 窗口长度；

如果恰好有一个更新数据从窗口中被移除，但是没有新的更新数据到来，请调整总和：

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

（注意，是将其时间戳修改为上一个窗口开始的。如果恰好有一个更新进入窗口，但没有新的更新掉落，请按以下方式调整）：

sum += previously_most_recent_update.value * corresponding_time_to_next_update. 

如您所见，这只是一个大致的草图，但希望它能展示出如何在摊销基础上仅需O(1)个操作来维护平均值。但请注意前一个段落中的进一步优化。还要注意旧回答中提到的稳定性问题，这意味着浮点误差可能会在大量此类增量操作中累积，从而导致与完整计算结果显著不同，这对应用程序非常重要。

- necromancer

Answer 2

如果近似值可以接受，并且样本之间有最小时间间隔，您可以尝试超采样。拥有一个数组，表示比最小间隔更短的均匀间隔时间，并在每个时间段存储最新接收到的样本。间隔越短，平均值越接近真实值。时间间隔应不大于最小间隔的一半，否则可能会错过样本。

- Mark Ransom

Answer 3

#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
}

- Robᵩ

---

谢谢你的回答。需要改进的一点是实际上“缓存”总平均值，这样我们就不必一直循环了。此外，可能是一个小问题，但使用双端队列或列表来存储值是否更有效率，因为我们假设更新将按正确顺序进行。插入比在映射中更快。 - 0x26res

是的，您可以缓存“sum”的值。减去您删除的样本值，添加您插入的样本值。此外，是的，deque<pair<Sample,Date>>可能更有效率。我选择了map以提高可读性，并且可以轻松调用map::upper_bound。一如既往，先编写正确的代码，然后对其进行分析和测量增量更改。 - Robᵩ

Answer 4

注意: 显然这不是正确的方法。在此留下参考，以了解这种方法的问题所在。请查看评论。

更新-基于Oli的评论...不过我不确定他所说的不稳定性是什么。

使用按“到达时间”排序的映射与值。在值到达时，将到达时间添加到已排序的映射中，以及它的值，并更新移动平均值。

警告：这是伪代码：

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下面的评论。

- Dennis

---

这个不行：它没有考虑每个值存在于窗口长度的比例。此外，这种加法然后减法的方法只适用于整数类型，而不适用于浮点数。 - Oliver Charlesworth

@OliCharlesworth - 抱歉，我在说明中错过了一些重要的要点（双倍和时间加权）。我会进行更新。谢谢。 - Dennis

时间加权是另一个问题。但这不是我要谈论的。我指的是当一个新值首次进入时间窗口时，它对平均值的贡献很小。它的贡献会继续增加，直到有一个新值进入。 - Oliver Charlesworth

Shirely现在可以针对剩余数值简单地应用任何他需要的算法了吗？他已经拥有了所有需要的信息......数值的数量，它们的值以及到达时间。 - Dennis

我不认为你可以仅仅通过事件总数来进行除法运算，你必须要通过时间跨度来进行除法运算。希望在calculateRunningTotal函数中应用的加权值能够解决这个问题。 - Mark Ransom