英文:
Algorithm for counting things by the second and maintaining a running average
问题
我想按照特定属性计算请求的数量，并按照一定的时间段（可能是按秒）进行汇总，然后对过去10秒、过去2分钟等时间段进行运行平均值/最大值/最小值。
对我来说，显而易见的方法是只需拥有一个秒数列表，当我需要移动/运行平均值时，只需在列表中回溯适当的时间量并计算平均值。除了一些明显的优化措施，如存储聚合值以供更长时间段使用，我还缺少哪些想法？
英文:
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?
答案1
得分: 8
我更喜欢“指数移动平均”，因为它更简单，不需要将值保存在数组中。
以下是我过去使用的函数：
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
英文:
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
答案2
得分: 6
我对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
英文:
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
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论