Вычисление количества сообщений в секунду в прокручивающемся окне?
У меня есть сообщения, входящие в мою программу с разрешением миллисекунды (где угодно от нуля до пары сотни сообщений миллисекунда).
Я хотел бы сделать некоторый анализ. А именно, я хочу поддержать несколько прокручивающихся окон количеств сообщения, обновленных, поскольку сообщения входят. Например,
- # из сообщений в прошлую секунду
- # из сообщений в последней минуте
- # из сообщений в прошлое полчаса, разделенное на # сообщений в прошлый час
Я не могу только поддержать простое количество как "1 017 сообщений в прошлую секунду", так как я не буду знать, когда сообщение будет более старым, чем 1 секунда и поэтому больше не должно быть в количестве...
Я думал о поддержании очереди всех сообщений, поиск самого молодого сообщения, это является более старым, чем одна секунда, и выведение количества от индекса. Однако это кажется, что было бы слишком медленно, и съест большую память.
Что я могу сделать для отслеживания эти количества в моей программе так, чтобы я мог эффективно получить эти значения в режиме реального времени?
5 ответов
Легче всего с этим справляется циклический буфер.
Циклический буфер имеет фиксированное количество элементов и указатель на них. Вы можете добавить элемент в буфер, и когда вы это делаете, вы увеличиваете указатель на следующий элемент. Если вы выходите за пределы буфера фиксированной длины, вы начинаете с самого начала. Это эффективный с точки зрения пространства и времени способ хранения "последних 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;
}
Для последнего миллисекунды вести счет. Когда миллисекундный срез переходит к следующему, сбросьте счетчик и добавьте счетчик в массив буфера прокрутки миллисекунд. Если вы сохраните это накопительное, вы можете извлекать количество сообщений в секунду с фиксированным объемом памяти.
По завершении 0,1-секундного среза (или другого небольшого значения рядом с 1-й минутой) просуммируйте последние 0,1 * 1000 элементов из массива скользящих буферов и поместите их в следующий скользящий буфер. Таким образом, вы можете сохранить буфер прокрутки миллисекорды маленьким (1000 элементов на максимум 1 с) и буфер для поиска в минуту (600 элементов).
Следующий трюк можно проделывать целые минуты с интервалом в 0,1 минуты. Все заданные вопросы могут быть заданы путем суммирования (или при использовании накопительного вычитания двух значений) нескольких целых чисел.
Единственным недостатком является то, что значение последней секунды будет изменяться каждые мс, а значение минуты - только каждые 0,1 секунды, а значение часа (и производные с% за последние 1/2 часа) - каждые 0,1 минуты. Но, по крайней мере, вы сдерживаете использование памяти.
Я подумал о ведении очереди всех сообщений, поиске самого молодого сообщения старше одной секунды и выводе счетчика из индекса. Однако это кажется слишком медленным и потребляет много памяти.
Лучшей идеей было бы поддерживать связанный список сообщений, добавлять новые сообщения в заголовок (с отметкой времени) и извлекать их из хвоста по мере истечения срока их действия. Или даже не вытаскивать их - просто держите указатель на самое старое сообщение, пришедшее в желаемый период времени, и продвигайте его к началу, когда это сообщение истечет (это позволяет вам отслеживать умножение таймфреймов с одним списком).
Вы можете вычислить счет, когда это необходимо, пройдя от хвоста к голове, или просто сохранить счет отдельно, увеличивая его каждый раз, когда вы добавляете значение в голову, и уменьшая его всякий раз, когда вы продвигаете хвост.
Окно скользящего дисплея может обновляться только так быстро, скажем, вы хотите обновлять его 10 раз в секунду, поэтому для данных за 1 секунду вам потребуется 10 значений. Каждое значение будет содержать количество сообщений, появившихся за эту 1/10 секунды. Назовем эти значения ячейками, каждая ячейка содержит 1/10 секунды данных. Каждые 100 миллисекунд одна из корзин сбрасывается, и новая корзина устанавливается на количество сообщений, появившихся за эти 100 миллисекунд.
Если вы хотите сохранить точность в 1/10 секунды в течение всего часа, вам понадобится массив из 36 КБ ячеек для хранения информации о частоте сообщений за час. Но это кажется излишним.
Но я думаю, что было бы разумнее снизить точность по мере увеличения интервала времени.
Может быть, вы храните данные за 1 секунду с точностью до 100 миллисекунд, за 1 минуту с точностью до секунды, за 1 час с точностью до минуты и так далее.
Вам нужно экспоненциальное сглаживание, иначе известное как экспоненциальное взвешенное скользящее среднее. Возьмите EWMA времени с момента получения последнего сообщения, а затем разделите это время на секунды. Вы можете запустить несколько таких моделей с разными весами, чтобы охватить эффективно более длинные временные интервалы. По сути, вы используете бесконечно длинное окно, поэтому вам не нужно беспокоиться об истечении данных; уменьшающиеся веса делают это за вас.