小硬核：你知道任何並行修改的移動平均算法嗎？

Question

你知道任何並行修改的移動平均算法嗎？

我想快速計算移動平均線，但不想用sequential algorithms。我想使用並行算法，但我還沒有找到解決方案。

最好的算法，我發現是順序算法modified moving average for measuring computer performance：

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) 

其他一些算法也不錯，但我還沒有找到並行算法。

這是一個很難的問題，我需要一些幫助。

考慮，我想指望這會在隨機時間順序的事件 - 早期事件可以稍後，延遲事件 - 你可以假設早期事件，可以跳過/後期加工事件之後變得過時（或一些超時）。 不假定事件的連續時間順序和事件從同一時間將與同一時間來。

---

我不希望使用任何算法需要記住許多樣品（特別是全部）應該只記得一次和以前的平均值也許一些額外的價值而不是全部或同一樣品。考慮到算法可以使一些小的錯誤不需要完美，如果它的原因是一些性能提升。

這將是非常好的，如果它將使用分片，但不是必需的。

Answer 1

具有並行算法的可能性取決於您正在使用的移動平均值的性質。

您在問題中顯示的算法是指數平滑器。因此，數據的第一個值對每個計算的平均值都有影響。第一個數值對每個新數據點的影響量都會減小，但即使序列中的最後一個平均數也會受到第一個數據點的輕微影響。

這種移動平均數不能平行，因爲如果不明確或隱含地使用已經收到的所有先前數據，則無法計算任何平均值。

但是，移動平均數的維基百科的article很好地總結了一系列移動平均方法，其中一些方法很容易並行執行。

例如，一個簡單的移動平均採用以下形式（用於奇數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項計算的並行m項與p螺紋的數據集的移動平均值爲p的子序列，其中的每一個重疊於下一個和前（除了第一個和最後的子序列）的子 - 由int(n/2)數據點序列，並讓每個線程計算其子序列的移動平均值。

您可以在問題Simple Moving Average summation/offset issue及其答案中找到該算法的高效順序實現（適用於並行實現的每個線程）。該方法計算了一個尾隨移動平均線，而不是我上面顯示的（可以優先考慮的）位於中心位置的移動平均線。也就是說，它把我在上面計算的值代入moving_average[i+n2]而不是moving_average[i]。

**這留下擱置的可能性，即，數據可以是在不規則的時間間隔。你已經顯示的方法解決了問題，並且可以在其他方法中以相同的方式處理它。

Answer 2

均線，事件到達順序可以做這樣的：

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

其中n決定這個樣本應該有多大（或很少）影響對均線。影響越大，n越小。隨着時間的推移，隨着新樣本的到來，舊樣本對移動平均值的影響將越來越小。

隨着樣本無序您可以嘗試通過讓樣本的年齡決定它對移動平均值有多大影響來模擬該行爲。這可以例如就像這樣：

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

如果我讓sampleAge支配newSample應有多大影響的移動平均值。