计算滚动窗口中每秒的消息数？ [英] Calculating number of messages per second in a rolling window?

问题描述

我以毫秒级的分辨率（从零到几百毫秒不等）进入程序的消息。

I have messages coming into my program with millisecond resolution (anywhere from zero to a couple hundred messages a millisecond).

我想做一些分析。具体来说，我想保持消息计数的多个滚动窗口，并随着消息的传入而更新。例如，

I'd like to do some analysis. Specifically, I want to maintain multiple rolling windows of the message counts, updated as messages come in. For example,

• 最后的消息数第二分钟


• 最近一分钟的消息数量


• 最后半小时的 #em除以个消息数量上一小时

• # of messages in last second
• # of messages in last minute
• # of messages in last half-hour divided by # of messages in last hour

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

I can't just maintain a simple count like "1,017 messages in last second", since I won't know when a message is older than 1 second and therefore should no longer be in the count...

我想到了将所有消息，搜索大于一秒的最年轻消息，然后从索引中推断出计数。但是，这似乎太慢了，会消耗很多内存。

I thought of maintaining a queue of all the messages, searching for the youngest message that's older than one second, and inferring the count from the index. However, this seems like it would be too slow, and would eat up a lot of memory.

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

What can I do to keep track of these counts in my program so that I can efficiently get these values in real-time?

推荐答案

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

This is easiest handled by a cyclic buffer.

循环缓冲区具有固定数量的元素和一个指向它的指针。您可以将元素添加到缓冲区中，然后，将指针增加到下一个元素。如果超过了定长缓冲区，则从头开始。这是一种节省时间和空间的方法，可以存储最后N个项目。

A cyclic buffer has a fixed number of elements, and a pointer to it. You can add an element to the buffer, and when you do, you increment the pointer to the next element. If you get past the fixed-length buffer you start from the beginning. It's a space and time efficient way to store "last N" items.

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

Now in your case you could have one cyclic buffer of 1,000 counters, each one counting the number of messages during one millisecond. Adding all the 1,000 counters gives you the total count during last second. Of course you can optimize the reporting part by incrementally updating the count, i.e. deduct form the count the number you overwrite when you insert and then add the new number.

您可以然后使用另一个具有60个时隙的循环缓冲区，并以整秒为单位计算消息总数；每秒一次，获取毫秒缓冲区的总数，并将该计数写入具有秒分辨率等的缓冲区中。

You can then have another cyclic buffer that has 60 slots and counts the aggregate number of messages in whole seconds; once a second, you take the total count of the millisecond buffer and write the count to the buffer having resolution of seconds, etc.

此处类似于C的伪代码：

Here C-like pseudocode:

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;
}

这篇关于计算滚动窗口中每秒的消息数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！