假设您有一个不断获取 HTTP 请求的服务器。你的老板需要一些统计数据，并要求你计算在任何给定时间最后一分钟内的命中数。
你会使用什么算法和数据结构来实现这一点？
问问题
4545 次
2 回答
7
使用循环缓冲区。
每当您必须通过内置的过时来保留一些当前统计信息时，环形缓冲区是一个不错的选择。在您的情况下，您可以通过在循环缓冲区的前面插入新数据包并在缓冲区中保留一分钟前指针，或对请求时间执行二进制搜索，轻松地保持最后一分钟的请求计数.
于 2012-07-28T12:44:43.203 回答
1
一个动态数组，其中一个仅附加文件是磁盘上的对应文件。只需将每个命中附加到数组中，以便按时间排序。追加需要摊销的常数时间。您可以进行二分搜索（或插值搜索）以找到最后一分钟开始的点，然后在 O(lg n ) （或 (O(lg lg n )) 时间内求和到最后。
或者，从末尾进行线性扫描而不是二进制搜索，如果文件变得非常大并且您只需要最后一分钟，这会更快。如果最后一分钟的预期命中次数与时间无关，则这只需要恒定的时间（但向后读取旋转磁盘上的文件可能会很慢）。
如果您没有空间来存储所有旧数据，那么使用双端队列是一个更好的主意。deques 的良好实现在标准库中可用，例如 C++ 和 Python。
于 2012-07-28T12:34:42.327 回答