algorithm - 计算滚动窗口中每秒的消息数？

Question

我的程序中有消息以毫秒为单位(每毫秒从零到几百条消息不等)。

我想做一些分析。具体来说，我想维护消息计数的多个滚动窗口，随着消息的到来而更新。例如，

• 上一秒的消息数
• 最后一分钟的消息数
• 过去半小时内的消息数除以过去一小时内的消息数

我不能只维护一个简单的计数，例如“最后一秒有 1,017 条消息”，因为我不知道消息何时超过 1 秒，因此不应再出现在数...

我考虑维护所有消息的队列，搜索早于一秒的最新消息，并从索引推断计数。但是，这似乎太慢了，而且会占用大量内存。

我该怎么做才能在我的程序中跟踪这些计数，以便我可以有效地实时获取这些值？

Answer 1

这是循环缓冲区最容易处理的。

循环缓冲区具有固定数量的元素和指向它的指针。您可以将一个元素添加到缓冲区，当您这样做时，您会增加指向下一个元素的指针。如果你通过了固定长度的缓冲区，你就从头开始。这是一种节省空间和时间的方式来存储“最后 N”项。

现在，在您的情况下，您可以拥有一个包含 1,000 个计数器的循环缓冲区，每个计数器计算一毫秒内的消息数。将所有 1,000 个计数器相加即可得出最后一秒的总计数。当然，您可以通过增量更新计数来优化报告部分，即从计数中减去插入时覆盖的数字，然后添加新数字。

然后你可以有另一个循环缓冲区，它有 60 个槽，并计算整秒内的消息总数；每秒一次，您获取毫秒缓冲区的总计数，并将计数写入具有秒等分辨率的缓冲区。

这里是类 C 的伪代码:

int msecbuf[1000]; // initialized with zeroes
int secbuf[60]; // ditto
int msecptr = 0, secptr = 0;
int count = 0;
int msec_total_ctr = 0;
void msg_received() { count++; }
void every_msec() {
  msec_total_ctr -= msecbuf[msecptr];
  msecbuf[msecptr] = count;
  msec_total_ctr += msecbuf[msecptr];
  count = 0;
  msecptr = (msecptr + 1) % 1000;
}
void every_sec() {
  secbuf[secptr] = msec_total_ctr;
  secptr = (secptr + 1) % 60;
}