Windowless moving percentileをgoで実装してみる

Windowless moving percentileとは指数平滑移動平均(Exponential moving average)をベースにしたパーセンタイル値の予測方法で 名前の通り、windowlessということで、windowなしにパーセンタイルの予測が可能で、メモリ効率や計算効率が良い。 windowとは、固定サイズの直近の観測値を集めた配列で、その配列の長さは100より大きい値を選ぶことが多いそう。 それを必要としないということは、メモリに優しいことが分かる。

今回はこのWindowless moving percentileをgoで実装していく。

Windowless moving percentileはこの記事 にて説明が書かれている。 ここの記述をベースに実装する。

まずはexponential moving percentileを実装する

Windowless moving percentileの実装の前に、exponential moving percentile を実装する必要があるので まずはこれを実装する。

以下のようなコードになる。

type ExponentialMovingAverageState struct {
    r float64

    average float64

    count   int32
    count_min int32
}

func NewExpMovingAvg(r float64) *ExponentialMovingAverageState {
    count_min := int32(math.Trunc(math.Ceil(1 / r)))
    return &ExponentialMovingAverageState{
        r:       r,
        count_min: count_min,
    }
}

func (s *ExponentialMovingAverageState) Sample(x float64) {
    var alpha float64
    if s.count < s.count_min {
        s.count++
    }
    if s.count >= s.count_min {
        alpha = s.r
    } else {
        alpha = 1 / float64(s.count)
    }
    s.average = alpha * x + (1-alpha)*s.average
}

ユーザから渡された値 r (0 < r <= 1)を使って 指数平滑移動平均を計算していくことになる。 この値は新しい観測値をどの程度重み付けするか、という値になる。

この値は windowless moving percentileでも使われる。

次はMoving varianceを計算する構造体を実装する

次はmoving varianceを計算する構造体を実装する。といいつつ、サンプル実装だと標準偏差も計算している謎の型になっている・・・。

ほぼサンプルのままなので 説明は省くがソースコードだけは書いておく。

type ExponentialMovingVarianceState struct {
    average *ExponentialMovingAverageState
    variance *ExponentialMovingAverageState
 
    stdev float64
    normalized float64
}

func NewExpMovingVariance(alphaAvg, alphaVar float64) *ExponentialMovingVarianceState {
    return &ExponentialMovingVarianceState{
        average: NewExpMovingAvg(alphaAvg),
        variance: NewExpMovingAvg(alphaVar),
    }
}

func (s *ExponentialMovingVarianceState) Sample(x float64) {
    if s.average.count > 0 {
        s.variance.Sample(math.Pow(x - s.average.average, 2))
    }
    s.average.Sample(x)
 
    s.stdev = math.Sqrt(s.variance.average)
    if s.stdev != 0 {
        s.normalized = (x - s.average.average) / s.stdev
    }
}

Windowless moving percentileを実装してみる

ここで準備が整ったので 本命のWindowless moving percentile実装していく。

構造体の定義とその初期化関数としては以下のようになった。

type WindowlessMovingPercentileState struct {
    r float64
    p float64
    value float64
    delta float64
 
    deltaState *ExponentialMovingVarianceState
    count   int32
}

func NewWindowlessMovingPercentile(percentile float64, r, alphaAvg, alphaVar float64) *WindowlessMovingPercentileState {
    return &WindowlessMovingPercentileState{
        r: r,
        p: percentile,
        delta: r,
        deltaState: NewExpMovingVariance(alphaAvg, alphaVar),
    }
}

サンプル実装を参考に書いてみたところ、以下のような実装になった。

func (s *WindowlessMovingPercentileState) Sample(x float64) {
    if s.count < 2 {
        s.count++
    }
    s.deltaState.Sample(x)
    // s.count >= 2 の場合のみ stdevの値が利用可能になるので guardを入れている
    if s.count >= 2 {
        s.delta = s.deltaState.stdev * s.r
    }
    if s.count == 1 {
        s.value = x
    } else if x < s.value {
        s.value = s.value - s.delta / s.p
    } else if x > s.value {
        s.value = s.value + s.delta / (1 - s.p)
    }
}

特に難しいところはなさそうに見えますが コードを少し間違えていたりしてハマりました・・・。

というわけで単に写経してみたよって記事でした。

一応、Go playgroundに置いておきました。

play.golang.org

まとめ

今回はWindowless moving percentileを実装してみた。 このアルゴリズムNetflix/concurrency-limits の go実装である、go-concurrency-limits にリファレンスされているアルゴリズムだ。 windowlessということで、windowなしにpercentileの計算が出来るので メモリに優しく並行性制御が出来るようになる。

漸化式の非対称性が気になるので もう少し遊んでみようかなと思っています。

終わり。