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に置いておきました。
まとめ
今回はWindowless moving percentileを実装してみた。 このアルゴリズムは Netflix/concurrency-limits の go実装である、go-concurrency-limits にリファレンスされているアルゴリズムである。 windowlessということで、windowなしにpercentileの計算が出来るので メモリに優しく並行性制御が出来るようになる。
漸化式の非対称性が気になるので もう少し遊んでみようかなと思っています。
終わり。