Вычисление количества сообщений в секунду в окне качения?

Ответ 1

Это проще всего обрабатывать циклическим буфером.

Циклический буфер имеет фиксированное количество элементов и указатель на него. Вы можете добавить элемент в буфер, и когда вы это сделаете, вы увеличиваете указатель на следующий элемент. Если вы пройдете через буфер фиксированной длины, вы начнете с самого начала. Это пространство и время, эффективный способ хранения "последних N" элементов.

Теперь в вашем случае у вас может быть один циклический буфер из 1000 счетчиков, каждый из которых подсчитывает количество сообщений в течение одной миллисекунды. Добавление всех счетчиков 1000 дает вам общее количество за последнюю секунду. Конечно, вы можете оптимизировать отчетную часть путем постепенного обновления счетчика, т.е. Вычесть из числа число, которое вы перезаписываете, когда вы вставляете, а затем добавляете новый номер.

Затем вы можете иметь еще один циклический буфер, который имеет 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;
}

Ответ 2

Вы хотите экспоненциальное сглаживание, иначе известное как экспоненциально взвешенная скользящая средняя. Возьмите EWMA времени с момента последнего сообщения, а затем разделите это время на секунду. Вы можете запустить несколько из них с разными весами, чтобы эффективно использовать длительные интервалы времени. Фактически, вы используете бесконечно длинное окно, поэтому вам не нужно беспокоиться об истечении срока действия данных; уменьшающие веса делают это для вас.

Ответ 3

Ваше текущее окно отображения может обновляться настолько быстро, что вы хотите обновить его 10 раз в секунду, поэтому для данных на 1 секунду вам понадобится 10 значений. Каждое значение будет содержать количество сообщений, появившихся за 1/10 секунды. Позволяет вызывать эти ячейки значений, каждый бит хранит 1/10 второго значения данных. Каждые 100 миллисекунд один из бункеров отбрасывается, а новый бит установлен на количество сообщений, отображаемых за 100 миллисекунд.

Вам понадобится массив из 36-килобайтных бункеров для хранения информации о скорости вашего сообщения за час, если вы хотите сохранить точность 1/10 секунды в течение всего часа. Но это кажется излишним.

Но я думаю, что было бы разумнее, чтобы точность снижалась по мере увеличения времени.

Возможно, вы сохраняете данные на 1 секунду с точностью до 100 миллисекунд, данные на 1 минуту с точностью до второй, с точностью до 1 часа с точностью до минуты и т.д.

Ответ 4

Для последнего миллисекунда держите подсчет. Когда срез миллисекунды переходит к следующему, reset подсчитывает и добавляет счет в миллисекундный буферный массив. Если вы сохраните этот кумулятивный, вы можете извлечь # сообщений/секунду с фиксированным объемом памяти.

Когда выполняется 0,1-секундный срез (или какое-либо другое маленькое значение около 1 минуты), суммируйте последние 0,1 * 1000 элементов из массива буферизирующего буфера и поместите его в следующий буфер перемотки. Таким образом, вы можете сохранить миллисекундный буфер перекачки маленьким (1000 элементов для поиска в 1 м) и буфером для поиска в минуту (600 элементов).

Вы можете сделать следующий трюк в течение целых минут 0,1 минут. Все вопросы могут быть заданы путем суммирования (или при использовании кумулятивного, вычитания двух значений) нескольких целых чисел.

Единственным недостатком является то, что последнее значение секунды wil изменяет каждые миллисекунды и минутное значение только каждые 0,1 с и значение часа (и производные с% за последние полчаса) каждые 0,1 минуты. Но, по крайней мере, вы не можете использовать память.

Ответ 5

Я думал о том, чтобы поддерживать очередь всех сообщений, ища самое младшее сообщение, которое было более одной секунды, и вывести счет из индекса. Тем не менее, похоже, что это будет слишком медленно, и будет много памяти.

Лучшей идеей было бы поддерживать связанный список сообщений, добавлять новые сообщения в голову (с меткой времени) и выталкивать их из хвоста по мере их истечения. Или даже не выталкивать их - просто держите указатель на самое старое сообщение, которое появилось в нужный таймфрейм, и продвигайте его по направлению к голове, когда это сообщение истекает (это позволяет отслеживать множественные таймфреймы с одним списком).

Вы можете вычислить счет, когда это необходимо, идя от хвоста к голове, или просто храните счет отдельно, увеличивая его, когда вы добавляете значение в голову, и уменьшаете его всякий раз, когда вы продвигаете хвост.