4

你知道任何并行修改的移动平均算法吗？

我想快速计算移动平均线，但不使用顺序算法。我想使用并行算法，但我仍然没有找到解决方案。

我发现的最好的算法是用于测量计算机性能的顺序算法修改移动平均值：

new_avg =  alfa(new_time, previous_time) * new_value + (1-alfa(new_time, previous_time)) * previous_avg

alfa(new_time, previous_time) = 1- exp(-(new_time - previous_time)/moving_period)

其他一些算法也不错，但我还没有找到并行算法。

这是一个很难的问题，我需要一些帮助。

考虑到我想要计数以随机时间顺序出现的事件 - 早期事件可能会晚于晚期事件 - 您可以假设在处理晚期事件（或超时）后早期事件可以被跳过/变得过时。不假设事件的顺序时间顺序，并且来自同一时间的事件将与同一时间发生。

我不想使用任何需要记住许多样本（尤其是所有样本）的算法，它应该只记住时间和以前的平均值，可能是一些附加值，而不是所有或相同的样本。考虑到算法可能会产生一些小错误，如果它的原因是一些性能提升，则不需要完美。

如果它会使用分片但不是必需的，那将是非常好的。

4

2 回答 2

5

事件按顺序到达的移动平均线可以这样完成：

newMovingAverage = ((MovingAverage * (n - 1)) + newSample) / n

wheren决定了这个样本对移动平均线的影响有多大（或小）。越大n，影响越小。随着时间的推移，随着新样本的到来，旧样本对移动平均线的影响将越来越小。

对于不按顺序出现的样本，您可以通过让样本的年龄决定它对移动平均线的影响程度来尝试模仿这种行为。这可以例如这样完成：

influence = (1 + sampleAge)^2 * n 
newMovingAverage = ((MovingAverage * (influence - 1)) + newSample) / influence

我让sampleAge指示newSample应该影响移动平均线的程度。

于 2013-05-07T23:17:13.723 回答
4

使用并行算法的可能性取决于您使用的移动平均线的性质。

您在问题中显示的算法是指数平滑器。因此，数据的第一个值对每个计算的平均值都有影响。第一个值的影响量随着每个新数据点的增加而减少，但即使是序列中的最后一个平均值也会受到第一个数据点的轻微影响。

这种移动平均线不能并行化，因为如果不使用（显式或隐式）之前收到的所有数据，就无法计算任何平均值。

然而，维基百科关于移动平均线的文章很好地总结了一系列移动平均线方法，其中一些很容易并行实现。

例如，一个简单的移动平均线采用以下形式（奇数n）**：

n2 = int(n/2)
moving_average[i] = (data[i-n2] + data[i-n2+1] ... + 
    data[i] + ... + data[i+n2-1] + data[i+n2])/n

此方法不使用早于int(n/2)点之前的任何数据i来计算点的移动平均值i。因此，您可以通过将项目划分为子序列来计算与线程m并行的项目数据集的移动平均值，其中每个子序列与数据的下一个和上一个（第一个和最后一个子序列除外）子序列重叠点，并让每个线程计算其子序列的移动平均值。pmpint(n/2)

您可以在问题简单移动平均求和/偏移问题及其答案中找到该算法的有效顺序实现（这将适用于并行实现的每个线程） 。该方法计算的是尾随移动平均线，而不是我上面展示的（可以说是首选的）位于中心的移动平均线。也就是说，它将我上面计算的值放在moving_average[i+n2]而不是 at moving_average[i]。

** 这排除了数据可能处于不规则时间间隔的可能性。您展示的方法解决了该问题，并且可以在其他方法中以相同的方式处理。

于 2013-05-07T21:16:13.687 回答