快速计算传入数字的最小值,最大值和平均值

Question

该计划每秒接收大约50,000个号码.

在任何给定时刻,我需要计算在最后一秒(关于给定时刻)到达的值(数字)的最小值,最大值和平均值.

有没有办法在不使用数组或列表(缓冲区)存储到达的数字和计算结果的情况下执行此操作？

如果我需要使用缓冲区,那么实现这一目标的有效方法是什么？

(请注意,缓冲区中的数字也必须不时有效删除)

Answer 1

这是一种在某些情况下可以有效地节省效率的算法:

1. 随着事件的进来,完全缓冲它们,并计算运行sum,count,min,max(微不足道).

2. 当一个请求为average,min或max制成,循环通过从缓冲器的背面和开始去除超过一秒年长值.从中减去sum并随时减去count.

   • 如果价值都高于min你可以保持你的min.如果值低于max,您可以保留max.在这种情况下,你有average,min和max有效地更新.

   • 如果值低于min或高于max,则需要遍历数组的其余部分并重新计算.

3. 每隔一秒执行一次左右,以便缓冲区不会太满.此代码也可以在每个缓冲区插入上执行,或者在任何有意义的地方执行.

这种工作的最佳结构是循环缓冲区,以避免内存分配和GC阻碍.它应该足够大,以涵盖每秒消息大小的最坏情况.

更新

根据使用场景,另一件事要做的是运行上面的算法,但是以10 x 100ms的块而不是1 x 1000ms的块.也就是说,保持这10个块的运行最小值,最大值,总和和计数.然后,当您达到"无效"方案时,通常只需要查看最新的100毫秒数据或快速通过其他9个块的最小值和最大值.

@ ja72提供了一个好主意,如果它们无效,可以节省查找最小值和最大值:

而不是保持最小/最大值x_min,x_max而是保持它们在具有i_min和i_max的x [i]阵列中的位置的索引.然后有时候找到它们是微不足道的,但是当考虑的最后一个值保持最小值和最大值时,需要扫描整个列表以建立新的限制.

Sam Holder在评论中有另一个好主意 - 保持一个总是排序的并行数组,这可以让你从顶部或底部删除数字,以便更容易找到新的最小值和最大值.但是,这里的插入速度有点受损(需要按顺序保留).

最终,正确的选择将取决于该计划的使用特征.值的读取频率与插入频率的频率如何？

Answer 2

使用循环缓冲区,每个元素都有时间戳和数据,每秒最大元素数作为循环缓冲区的大小.

当每个元素插入缓冲区头时,检查缓冲区另一侧的到期时间,删除元素.

如果删除的元素是最小值或最大值,则必须计算新的最小值/最大值.如果不是,您将根据新到货时间更新最小值/最大值.

对于平均值,保持总数,保持计数和除法.