Algorithm for counting things by the second and maintaining a running average

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 prefer exponential moving average as it is simpler and does not require to keep values in array

Here is function I used in past

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

and code example

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

Answer 2

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