算法 – 如何计算最后的秒,分和小时的请求数

拥有所有请求的链接列表和3个计数 – 最后一小时，最后一分钟和最后一秒。

一分钟前和之前，你将有2个指针到链表中。

一小时前将列在名单的末尾。无论何时最后一次请求的时间超过当前时间之前的一个小时，将其从列表中删除并减少小时数。

分和秒指针将分别指出分别在一秒钟之后发生的第一个请求。无论何时请求时间超过当前时间之前的一分钟以上，请向上移动指针并减小分/秒计数。

当新的请求进入时，将其添加到所有3个计数，并将其添加到链表的前面。

对计数的请求只需要返回计数。

所有上述操作都是恒定的时间。

如果小于100％的准确度是可以接受的：

由于上面已经是不变的时间了，所以你不能得到任何东西比这更快。然而，空间复杂性可能会有所不同，这取决于你通常会得到的每秒的请求数量;您可以通过以下方式轻微牺牲精度来减少此事：

具有如上所述的链接列表，但仅在最后一秒。也有3个计数。

然后具有60个元素的圆形数组，指示最近60秒的每个的计数。每当第二次通过时，从分钟计数中减去数组的最后(最旧的)元素，并将最后一个第二个计数添加到数组。

在过去60分钟内有一个类似的圆形阵列。

精确度损失：一秒钟内所有请求都可以关闭分钟计数，一分钟内所有请求都可以关闭小时计数。

显然，如果您每秒只能有一个请求，那么这并不真实。在这种情况下，您可以在链表中保留最后一分钟，最后60分钟只能有一个圆形数组。

还有其他变化 – 空间使用率的精度可以根据需要进行调整。