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

Question

我想按某些属性对请求进行计数，并按一定时间段（可能是第二个时间）对请求进行汇总，然后在过去10秒钟，过去2分钟等中运行平均值/最大值/分钟。（对我而言）最明显的方法是仅列出秒数，当我需要移动/运行平均值时，只需在列表中返回适当的时间并计算平均值即可。除了在存储汇总值以供更长的时间使用方面进行一些明显的优化之外，我还缺少什么主意？

Answer 1

我对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