排队方法

• 使用队列。

• 每当收到新请求时，将其入队。

• 每当我们需要获取最后一分钟的请求数时，请先将超过一分钟之前发生的所有条目从队列中取出（这是可行的，因为队列中的条目是按顺序插入的，因此对队列进行了排序）。然后返回队列的大小（可以O(1)通过存储变量来返回大小）。

• 由于您说每秒有很多请求，因此 每当您收到新请求时 ，您也可以 使旧条目出 队，这应该使队列保持在正确的大小附近，从而最大程度地减少了计数操作所花费的时间。

这将是O(k)两个入队和获得计数，其中k是发生在长度的任何时间内请求的最大数t，其中t任何两个请求之间的最大持续时间（作为一个例子，如果我们在以下毫秒的请求：1,2,3,5,15,20，最大持续时间为20-15 = 5，以5毫秒为单位的最大请求数为4（即1,2,3,5，在期间内发生的1-5）。

• 一种替代方法是让 计时器 运行 以使旧条目出队 。

其性能将O(1)用于排队以及O(m)计时器运行和获取计数，其中m是在任何长度的时间段内等于计时器频率的最大请求数。例如，1,2,3,5,15,20以6毫秒为单位的计时器间隔再次使用。以6毫秒为单位的最大请求数将是4（即1,2,3,5，在期间内发生1-6）。

这是“大数据”吗？

好吧，这实际上取决于您每秒收到的请求数。对于大数据，我们通常会谈论许多terrabyte的数据（随着计算机功能的增强，数据还会增加），我不认为只有最后一分钟的请求会接近这些数字。

基于计数的方法

如果您对小错误感到满意，可以执行以下操作：

有一个固定大小的队列（比方说60，每个元素表示对给定秒数的请求-是一个简单的整数值）。这可以实现为圆形数组。

令count=一个变量，指示最后一秒的请求数，已初始化为0。

有一个变量，用于存储最后一个请求的第二个值（以便能够确定队列中的元素用于哪一秒）。

当我们收到一个新请求时，请使所有表示秒的时间比一分钟前更长的元素出队，count以出队值递减，并与一起增加队列的后面（最后插入的值）count。

当我们需要获取最后一秒的请求数时，将指示秒数比一分钟前更长的所有元素count出队，并以出队值递减，然后返回count。

假设我们的队列是固定大小的，那么每个操作最多将花费O(1)（或者，如果您愿意，队列的大小O(m)在哪里m）。

这将给您最多1秒的错误。您当然可以解决该错误。例如，如果您想要半秒的错误，只需将队列的大小加倍，然后每半秒转到下一个元素。