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

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