每秒计算事物并保持运行平均值的算法

Question

I want to count requests by certain attributes and summarize them by a certain time period (probably by the second) and then have running averages/max/min for last 10 seconds, last 2 minutes, etc.

The obvious (to me) approach is to just have a list of seconds and when I need the moving/running average then just go back in the list the appropriate amount of time and calculate the average. Other than some obvious optimizations around storing aggregated values to use for the longer time periods, what ideas am I missing?

Answer 1

I'm not really familiar with Go, so please excuse any strangeness in the following code. Adding an element to the rolling average should be O(1) in time. It uses O(n) in memory (a fixed amount).

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))
}

Output:

$ 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