Есть некоторый поток сообщений, идущий не равномерно.
Например, с 0 - 10 секунду может прийти 1 сообщение, в следующие 10 ещё 5, потом 10, потом 100 и т.д и опять наступит затишье.
В целях мониторинга хочется иметь представление о точном количестве полученных сообщений (скользящим окном) за крайнюю минуту.
Пояснение: если мы запрашиваем кол-во сообщений в 13:12:05, то должны получить кол-во сообщений с 13:11:05 по 13:12:05. Запрос в 13:12:57 отображает число сообщений с 13:11:57 по 13:12:57.
При этом не интересует сколько было получено две минуты назад, только реальные актуальные цифры. Допускается огрубление с точностью до секунды.
Ограничения: память O(1), сложность O(1), одна нитка выполнения.
Например, с 0 - 10 секунду может прийти 1 сообщение, в следующие 10 ещё 5, потом 10, потом 100 и т.д и опять наступит затишье.
В целях мониторинга хочется иметь представление о точном количестве полученных сообщений (скользящим окном) за крайнюю минуту.
Пояснение: если мы запрашиваем кол-во сообщений в 13:12:05, то должны получить кол-во сообщений с 13:11:05 по 13:12:05. Запрос в 13:12:57 отображает число сообщений с 13:11:57 по 13:12:57.
При этом не интересует сколько было получено две минуты назад, только реальные актуальные цифры. Допускается огрубление с точностью до секунды.
Ограничения: память O(1), сложность O(1), одна нитка выполнения.
p.s. я не знаю, существует ли какое-то классическое и/или единственно верное решение или нет, уже засыпая я смог придумать вполне приемлемое для меня решение, но которое расходует больше, чем 3-5 переменных.
7 комментариев:
В данном случае асимптотическая зависимость O(1) указывается для чего? Для количества сообщений поступающих в систему или для отчетного периода (минута)?
Если для количества сообщений, то можно хранить массив из 60 int'ов с количеством сообщений полученных в каждую секунду последней минуты. Раз в секунду перезаписывать самое старое значение количеством сообщений полученных в последнюю снеунду (cyclic buffer по факту). Получение количества поступивших в последнюю минуту сообщений можно сделать O(1) имея предрасчитанную сумму массива модифицируя ее при перезаписи последнего значения (отнять старое значение, прибавить новое).
@Denis
O(1) указывается для того, что всё равно сколько сообщений пришло за минуту - 1 или 1 млн
ровно такое же решение у меня и возникло у меня в голове - вопрос в том, а можно ли на одной нитке сделать ещё лучше ? без использования массива из 60 int'ов.
Надно конечно подумать еще, но интуиция подсказывает что не жертвуя секундной точностью не получится.
Я, собственно, практически зуб даю, что лучше не получится.
Пусть мы находимся в момент Х. Поскольку будущего мы не знаем заранее, вполне возможно, что в ближайшую минуту сообщений вообще не будет, но нас будут каждую секунду дергать с запросом кол-ва сообщений. Как мы сможем отвечать на этот вопрос, на запомнив все 60 чисел?
Руслан,
Поток второй вероятно не нужен. Имея 60 натуральных чисел для подсчета количества сообщений, натуральное число обозначающее TlastUpdate(время когда пришел последний запрос), а также синтетический объект сумму, мы можем за O(1) делать обе операции:
+register new request;
+get sum.
В таком случае обе операции должны обладать дополнительной функциональностью - помощь в подсчете, т.к. нам всегда необходимо отвечать лишь на вопрос - последняя минута, то 60 натуральных чисел будут использоваться только для обновления суммы, при этом инвариант такой что нужно выкинуть все данные с TlastUpdate по TrequestTime(максимум один пробег по массиву).
Бррр хорошая задачка на утро, а она никак не связана с более обширной - статистика за 1 минуту, 1 час и 4 часа?
Я пишу вот о чем. Пусть у нас есть "решатель" для этой задачи, и это некий черный ящик. Делаем с ним такой мысленный эксперимент: сначала даем на вход некоторую последовательность 60 чисел -- количеств сообщений в секунду. По прошествии 60 секунд каждую последующую секунду даем на вход 0, и спрашиваем "сколько пришло за последнюю минуту. Очевидно, из полученных на выходе 60 сумм можно восстановить все числа, "загруженные" в черный ящик в первую минуту. То есть, с точки зрения количества информации наш черный ящик должен хранить в себе объем информации эквивалентный 60 целым числам.
Отсюда я и делаю вывод, что меньше чем с int[60] не сделать
Отправить комментарий