我的程序中有消息以毫秒为单位(每毫秒从零到几百条消息不等)。
我想做一些分析。具体来说,我想维护消息计数的多个滚动窗口,随着消息的到来而更新。例如,
- 上一秒的消息数
- 最后一分钟的消息数
- 过去半小时内的消息数除以过去一小时内的消息数
我不能只维护一个简单的计数,例如“最后一秒有 1,017 条消息”,因为我不知道消息何时超过 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;
}
关于algorithm - 计算滚动窗口中每秒的消息数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2269924/