快速计算输入数字的最小值、最大值和平均值

Question

该程序每秒接收大约50000个数字。

在任何给定时刻，我都需要计算最后一秒到达的值（数字）的最小值、最大值和平均值（关于给定时刻）。

有没有办法不用数组或列表（缓冲区）来存储到达的数字和计算结果？

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

（请注意，缓冲区中的数字也必须不时有效地删除）

Answer 1

你不能把你的号码和到达时间以及当前的最大值排成一个队吗

然后当一个数字到达时，将其添加到队列中，并调整最小/最大/值和计数。然后查看队列的另一端，删除所有不在最后一个数字到达1秒内的元素，并再次调整最大/最小/计数/总值。

然后你不需要在瞬间计算任何东西，只需返回预先计算的内容（即读取最小/最大或总/计数的当前值）

正如@yaman指出的，你不能只保留最小和最大值，因为当一个被删除时，你可能不知道新的。在这种情况下，我可能会保留列表中所有数字的第二份副本，而不是按到达时间排序我会按价值订购。然后您只需添加和删除列表中的每个数字，这样您就可以始终知道最大值和最小值。这使您不必扫描缓冲区中的所有元素来查找新的最大/最小值，代价是保留2份副本，但是对该列表的更新应该很便宜，因为它已经订购了。

Answer 2

使用循环缓冲区，每个元素都有时间戳和数据，每秒的最大元素数是循环缓冲区的大小。

当每个元素插入缓冲区头部时，检查缓冲区另一侧的过期时间，删除该元素。

如果删除的元素是最小值或最大值，则必须计算新的最小值/最大值。如果不是，则根据新到达的元素更新最小值/最大值。

对于平均值，保持总数，保持计数，然后除以。

Answer 3

这里有一个算法，在某些情况下可以节省效率：

>

当事件进入时，将其完全缓冲，并计算一个正在运行的总和，计数，最小值，最大值（微不足道）。

当请求平均值、min或max时，从缓冲区后面循环，并开始删除超过一秒钟的值。减去和和计数。

>

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

每隔一秒钟左右执行一次第二步，这样缓冲区就不会太满。该代码也可以在每个缓冲区插入上执行，或者在任何有意义的地方执行。

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

更新

根据使用场景，另一件事是运行上面的算法，但以10 x 100毫秒的块而不是1 x 1000毫秒的块运行。也就是说，保持最小值，最大值，求和并计算这10个块。然后，当你到达一个“无效”场景时，你通常只需要查看最新的100ms数据，或者快速浏览其他9个数据块的最小值和最大值。

@ja72提供了一个很好的主意，如果最小值和最大值无效，可以节省寻找它们的费用：

x_max保留最小/最大值x_min，而是保留它们在x[i]数组中的位置的索引，i_min和i_max。然后找到它们有时可能是微不足道的，但是当考虑的最后一个值包含最小值和最大值时，需要扫描整个列表来建立新的限制。

山姆·霍尔德（Sam Holder）在评论中还有另一个好主意——保持一个总是排序的平行数组，这让你可以从顶部或底部删除数字，以更容易地找到新的最小值和最大值。但是，此处的插入速度有点降低（需要保持有序）。

最终，正确的选择将取决于程序的使用特性。读取值的频率与插入值的频率？