statistics - 秒単位でカウントし、移動平均を維持するアルゴリズム

Question

特定の属性ごとにリクエストをカウントし、特定の期間 (おそらく秒単位) でそれらを要約してから、過去 10 秒間、過去 2 分間などの平均/最大/分を実行したいと考えています。

（私にとって）明らかなアプローチは、秒のリストを作成し、移動/移動平均が必要な場合は、リストに戻って適切な時間を計算し、平均を計算することです。長期間使用する集計値の保存に関するいくつかの明らかな最適化以外に、どのようなアイデアが欠けていますか?

Answer 1

exponential moving averageよりシンプルで、値を配列に保持する必要がないため、私は好みます

ここに私が過去に使用した機能があります

func MovingExpAvg(value, oldValue, fdtime, ftime float64) float64 {
  alpha := 1.0 - math.Exp(-fdtime/ftime)
  r := alpha * value + (1.0 - alpha) * oldValue
  return r
}

およびコード例

http://play.golang.org/p/OZ25cwKMnT

Answer 2

私は Go にあまり詳しくないので、次のコードに奇妙な点があることをお許しください。ローリング平均に要素を追加する時間は O(1) である必要があります。メモリ内の O(n) を使用します (一定量)。

package main

import "fmt"

func rolling(n int) func(float64) float64 {
        bins := make([]float64, n)
        average := 0.0
        i := 0
        return func(x float64) float64 {
                average += (x - bins[i]) / float64(n)
                bins[i] = x
                i = (i + 1) % n
                return average
        }
}

func main() {
        add := rolling(5)
        add(1)
        add(2)
        add(3)
        add(4)
        fmt.Println("(1+2+3+4+5          ) / 5 =", add(5))
        fmt.Println("(  2+3+4+5+9        ) / 5 =", add(9))
        fmt.Println("(    3+4+5+9+3      ) / 5 =", add(3))
        fmt.Println("(      4+5+9+3+0    ) / 5 =", add(0))
        fmt.Println("(        5+9+3+0-9  ) / 5 =", add(-9))
        fmt.Println("(          9+3+0-9-8) / 5 =", add(-8))
}

出力：

$ go run roll.go
(1+2+3+4+5          ) / 5 = 3
(  2+3+4+5+9        ) / 5 = 4.6
(    3+4+5+9+3      ) / 5 = 4.8
(      4+5+9+3+0    ) / 5 = 4.2
(        5+9+3+0-9  ) / 5 = 1.6
(          9+3+0-9-8) / 5 = -1