高效的方法,可以实时计算最后一分钟内服务器的点击次数

Question

假设您有一台不断获取HTTP请求的服务器.你的老板需要一些统计数据,并要求你计算在任何给定时间内最后一分钟内的命中数.

您将使用什么算法和数据结构来实现这一目标？

Answer 1

使用循环缓冲区.

每当你必须保留一些内置过时的当前统计数据时,环形缓冲区是一个很好的候选者.在您的情况下,您可以通过在循环缓冲区的前面插入新数据包并在缓冲区中保留一分钟前指针或在请求时间执行二进制搜索,在最后一分钟轻松地保留请求的计数.

Answer 2

一个动态数组，其中一个仅附加文件是磁盘上的对应文件。只需将每个命中添加到数组中，这样它就按时间排序了。追加需要摊销常数时间。您可以进行二分搜索（或插值搜索）来找到最后一分钟开始的点，然后在 O(lg n ) （或 (O(lg lg n )) 时间内求和到结束。

或者，从末尾开始线性扫描而不是二进制搜索，如果文件变得非常大并且您只需要最后一分钟，则速度会更快。如果最后一分钟的预期点击次数与时间无关，则这只需要恒定的时间（但向后读取旋转磁盘上的文件可能会很慢）。

如果您没有空间来存储所有旧数据，那么使用双端队列是一个更好的主意。双端队列的良好实现可以在 C++ 和 Python 等标准库中找到。