程序每秒接收大约 50,000 个数字。
在任何给定时刻，我需要计算在最后一秒(关于给定时刻)到达的值(数字)的最小值、最大值和平均值。
有没有一种方法可以不使用数组或列表(缓冲区)来存储到达的数字和计算结果？
如果我需要使用缓冲区，实现此目的的有效方法是什么？
(请注意，缓冲区中的数字也必须不时有效地删除)
最佳答案
这是一种算法，在某些情况下可以在一定程度上节省效率:
随着事件的到来，将它们完全缓冲，并计算一个运行的
sum、count、min、max(琐碎)。当请求
average、min或max时，从缓冲区的后面循环并开始删除早于一秒的值。边做边减sum和count。如果所有值均高于
min，您可以保持min。如果值低于max，您可以保留max。在这种情况下，您可以高效地更新average、min和max。如果值低于
min或高于max，您将需要遍历数组的其余部分并重新计算它。
也大约每秒钟执行一次第二步，这样缓冲区就不会太满。此代码也可以对每个缓冲区插入执行，或者在任何有意义的地方执行。
这种工作的最佳结构是循环缓冲区，以避免内存分配和 GC 妨碍。它应该足够大以涵盖每秒消息大小的最坏情况。
更新
根据使用场景，另一件事是运行上面的算法，但以 10 x 100 毫秒的 block 而不是 1 x 1000 毫秒的 block 运行。也就是说，在这 10 个 block 上保持运行的最小值、最大值、总和和计数。然后，当您到达“无效”场景时，您通常只需要查看最新的 100 毫秒数据或快速浏览其他 9 个 block 的最小值和最大值。
@ja72 提供了一个好主意，可以节省查找无效的最小值和最大值的费用:
与保留最小值/最大值 x_min 不同，x_max 保留它们在 x[i] 数组中的位置索引，其中包含 i_min 和 i_max。有时找到它们可能很简单，但是当考虑的最后一个值包含最小值和最大值时，需要扫描整个列表以建立新的限制。
Sam Holder 在评论中提出了另一个好主意 - 保留一个始终排序的并行数组，这样您就可以从顶部或底部删除数字，以便更轻松地找到新的最小值和最大值。但是，此处的插入速度会有所降低(需要保持顺序)。
最终，正确的选择将取决于程序的使用特性。读取值的频率与插入值的频率是多少？
关于c# - 快速计算传入数字的最小值、最大值和平均值，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10288076/