«Потоковая» статистика?

Balancer> ...
Balancer> Есть что-то более корректное и изящное?

Есть интересный алгоритм для получения порядковой статистики (минимум, максимум, медиана или любой квантиль) от последних N принятых величин. Рецепт:

Берём бинарное сортирующее дерево. Для эффективности организуем его in-place в массиве размера N (как в heapsort), причём в массиве элементы располагаются в порядке следования по времени. Отдельно храним указатель на самый старый (N-й) элемент. Таким образом наша структура преставляет собой одновременно и дерево и циклический список и работа ведётся в фиксированном массиве без обращения к системе за новой памятью.

Алгоритм добавления нового элемента очевиден: по указателю выбираем самый старый элемент, удаляем его из дерева. На его место записываем новый. Вставляем его в дерево. Передвигаем указатель на следующий по времени прихода элемент.

Для получения элемента по его порядковому номеру требуется хитрая модификация дерева, описанная Кнутом в TAOCP в пункте 6.2.3 (третий том). Модификация заключается в добавлении одного поля RANK в узлы дерева и, соответственно, обновлении этого поля по заданному рецепту в алгоритмах поиска/вставки и удаления элементов. Плюс дополнительный алгоритм поиска элемента по его порядковому номеру (который очень похож на стандартный алгоритм поиска по ключу).

В итоге имеем решение, которое работает в фиксированном массиве размером N ячеек. На добавление новой величины и запроса порядковой статистики требуется O (log N) времени.

У меня есть реализация описанной схемы на C.

ssb> Есть интересный алгоритм для получения порядковой статистики (минимум, максимум, медиана или любой квантиль) от последних N принятых величин.

Не годится. N реально большое должно быть. Скажем, выборка за сутки, а отсчёты каждые 10 секунд. Памяти реально — единичные ячейки

При полном хранении какого-то числа отсчётов посчитать по любому классическому алгоритму не проблема. Со временем расчёта проблем нет

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

GOGI> А так мне кажется на 518 тысячах выборок все это приблизительное будет сильно врать.

Я ж и пишу приблизительно Мне не нужна полная точность.

GOGI> А что за железо такое?

Да всякое встраиваемое. И распределённое key-value.

GOGI> Я видел только алгоритм экспоненциального скользящего среднего

О! Это как раз, по сути, и есть то, что я в начале привёл. Только формула в другом виде. А суть та же — накопленное среднее и новое значение складываются долями.

GOGI> А что за железо такое?

Вот пример (один из). Есть тупые сенсоры газов MQ-XXX. Они реально очень тупые и просто показывают сопротивление подогретой подложки, которое меняется в зависимости от изменения концентрации целевых газов. Проблема в том, что правильные попугаи там не абсолютные, и относительные к сопротивлению в инертной атмосфере, X = R/R0. А это R0 имеет склонность со временем уплывать и сильно. Перекалибровывать периодически — не выход. Но концентрация измеряемых газов часто падает до нуля (типа, регулярное проветривание и т.п.), поэтому в качестве R0 можно брать минимум за период. Хоть за сутки, хотя можно/лучше и за больше, скажем, за месяц.

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

Хранить N последний значений, в общем, можно (вот и на графике в аттаче — там в RRD много истории), но это привлечение внешнего ресурса, система перестаёт быть автономной.

Вот первая идея, по аналогии с скользящим средним, медленно-медленно «подтягивать» минимум к средним величинам, но отбрасывать его к фиксированным значениям, если полученный минимум станет меньше. Надо попробовать, насколько на практике такой метод будет работать и сравнить его с «честным» на большой машине.

Так контроллер-то какой с датчика сигнал снимает.
Учитывая погрешность сенсора, вряд ли его сигнал имеет больше одного полезного байта.
Соответственно, чтобы иметь возможность, смотреть среднее, минимальное, максимальное за 100 секунд, тебе надо 10 байт на окно, чтобы за последние 1000 секунд еще плюс 10 байт и так далее. Ну что у тебя, 40 байт памяти не найдется в контроллере? Самое мелкое, с чем я работал - Attiny45, там и то 128 байт ОЗУ.

GOGI> Учитывая погрешность сенсора, вряд ли его сигнал имеет больше одного полезного байта.

Значения 0…1023 А если нормализовать, то как раз минимум нужно знать. Тупо загрублять же, отбрасывая младшие 2 бита — грубо выходит.

GOGI> Соответственно, чтобы иметь возможность, смотреть среднее, минимальное, максимальное за 100 секунд

Мне нужно за сутки, лучше — за неделю

GOGI> тебе надо 10 байт на окно, чтобы за последние 1000 секунд еще плюс 10 байт и так далее. Ну что у тебя, 40 байт памяти не найдется в контроллере?

И сенсора — 4. Так что в лоб надо, скажем, 4*7*86400/10 = ~236кБайт. Можно как-то прореживать, хранить N последних, а уже из них минимум и максимум записывать в следующие, более грубые секции — это тот же RRD вручную получается. Сложно, криво…

Плюс это не единственный способ применения. Например, данные пишутся в MQTT. Это простой key-value. В случае потоковой записи я могу подписаться на изменения ключа, читать среднее/минимальное, высчитывать новое и писать изменённый ключ. Автоматически идёт накопление статистики без потери данных на перезагрузках и т.п. Можно, конечно, в MQTT хранить по ключу сразу сериализованный массив, но жирно будет гонять туда/сюда каждый десяток секунд десятки (как минимум) килобайт сериализованных данных.

Balancer> Вот первая идея, по аналогии с скользящим средним, медленно-медленно «подтягивать» минимум к средним величина...

Здесь надо рассматривать не просто точки максимума и минимума, а точки локального максимума и минимума. Такие вещи ющутся через производные. Поэтому я бы контролировал момент смены знака градиента величины. Если меняется с + на - максимум, с - на + минимум. Чтобы не хватать всякие нанолокальные изменения величины градиент тоже надо усреднить. Как-то так

Alehandro> Здесь надо рассматривать не просто точки максимума и минимума, а точки локального максимума и минимума. Такие вещи ющутся через производные.

Давай потоковый метод вычисления производных без массивов

Alehandro>> Здесь надо рассматривать не просто точки максимума и минимума, а точки локального максимума и минимума. Такие вещи ющутся через производные.
Balancer> Давай потоковый метод вычисления производных без массивов

X'(i)=X(i) - X(i-1)
где X'(i) - значение i-го отчета производной 
X(i) - значение i-го отчета измеряемой величины
X(i-1) - значение i-1-го отчета измеряемой величины

Не совсем производная с точки зрения математики, но в твоей ситуации должно хватить. Для вычисления локального минимума и максимума надо знать 3 величины X'(i),X'(i-1), X(i-1). Чтобы во всякие локальные впадины не соваться, вместо X(i) - можно взять не саму измеряемую величину, а ее скользящее среднее (надо экспериментировать). Как я понял с вычислением скользящего среднего у тебя проблем нет.

Alehandro> Для вычисления локального минимума …

Кстати. Стоп. Мне минимум как раз не локальный нужен, а глобальный (на условном большом отрезке — неделя, например, 50 тыс. отсчётов)

Локальных минимумов у меня итак будет каждый день десяток…

Balancer>

Храним минимум и время. Получая очередной локальный минимум проверяем сколько прошло времени и если больше недели, теперь его ставим в качестве основного.

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

Можно придумать варианты когда он пропустит минимум но в реальных условиях алгоритм будет работать и нужно будет хранить только две переменных.

Alehandro>> Для вычисления локального минимума …
Balancer> Кстати. Стоп. Мне минимум как раз не локальный нужен, а глобальный (на условном большом отрезке — неделя, например, 50 тыс. отсчётов)
Balancer> Локальных минимумов у меня итак будет каждый день десяток…

Если рассматривать отрезок, точки экстремумов легко на концы отрезка лечь могут, что неправильно. Возьми локальность в пределах недели - кто мешает, шаг крупнее делай, при расчете производной бери например каждый сотый отчет, остальные херь. Или выкидывай младшие биты как GOGI предложил. Нулевые значения производной тоже выкидывай. Тебе же грубо говоря переворот производной ловить надо, а не абсолютное значение. Если есть дамп с отчетами, неплохо бы озвученные идеи в матлабе проверить прежде чем в железо код заливать.

PSS> Храним минимум и время.

Нет единого времени.

Alehandro> Если рассматривать отрезок, точки экстремумов легко на концы отрезка лечь могут, что неправильно.

Что ж тут неправильного? Если минимум был точно неделю назад, на границе отрезка, то он минимумом быть не перестаёт

Alehandro> Возьми локальность в пределах недели - кто мешает, шаг крупнее делай

Какой шаг? У меня нет массива данных. Есть только текущие значения. Ну и максимум 1-2 переменных.

Alehandro> Тебе же грубо говоря переворот производной ловить надо, а не абсолютное значение

Переворот производной — это локальный минимум Таких по десятку и больше в день будет. Сотня в неделю.

Alehandro> Если есть дамп с отчетами, неплохо бы озвученные идеи в матлабе проверить прежде чем в железо код заливать.

Да я, один фиг, на MQTT сперва тестировать буду

Balancer> А вот как аналогично считать минимальные и максимальные значения за период? Как считать минимум и максимум за всю историю — понятно, обычное условие. Но если данные имеют склонность «сдвигаться», то найденное максимальное и минимальное значение через какое-то время будут уже не актуальны.
Храни порядковый номер отсчёта для максимума и минимума. Когда максимум(минимум) покинут окно известной истории, пересчитай максимум(минимум).
100% корректный и универсальный способ, а дополнительные расходы вычмощи невелики, потому что такой пересчёт - редкое событие. И чем больше окно, тем больше расходы вычмощи, но и реже событие.

Вариация на эту тему - хранить и поддерживать стек максимумов и минимумов с участками неубывания/невозрастания отсчётов на случай пересчёта.

Татарин> Когда максимум(минимум) покинут окно известной истории, пересчитай максимум(минимум).

Пересчитать из чего? Ловить первый попавшийся минимум?

…

Но идея может сработать, если хранить, например, пару минимумов за два последних периода (хоть пусть и неделя последняя и неделя перед ней). Тогда по переполнению числа отсчётов просто переписываем последний минимум в предыдущий («глобальный») и начинаем считать последний минимум заново.

Татарин>> Когда максимум(минимум) покинут окно известной истории, пересчитай максимум(минимум).
Balancer> Пересчитать из чего? Ловить первый попавшийся минимум?
Ты совсем не хранишь отсчёты?

Balancer> Но идея может сработать, если хранить, например, пару минимумов за два последних периода (хоть пусть и неделя последняя и неделя перед ней). Тогда по переполнению числа отсчётов просто переписываем последний минимум в предыдущий («глобальный») и начинаем считать последний минимум заново.
Да, стек минимумов, стек максимумов.

Alehandro>> Если рассматривать отрезок, точки экстремумов легко на концы отрезка лечь могут, что неправильно.
Balancer> Что ж тут неправильного? Если минимум был точно неделю назад, на границе отрезка, то он минимумом быть не перестаёт

И зависит от разбиения на отрезки, что не правильно. Начало отрезка при старте только нужно, чтобы было отчего отталкиваться.

Alehandro>> Возьми локальность в пределах недели - кто мешает, шаг крупнее делай

Balancer> Какой шаг? У меня нет массива данных. Есть только текущие значения. Ну и максимум 1-2 переменных.

Шаг - разность индексов величин, которые для расчета используются. Бери каждый сотый отчет. Что ты берешь каждый сотый, что каждый первый - для расчета производной требуется помнить предыдущее значение: в одном случае это будет X(i-99), в другом X(i-1) - одна переменная, а не массив значений.

Alehandro>> Тебе же грубо говоря переворот производной ловить надо, а не абсолютное значение
Balancer> Переворот производной — это локальный минимум Таких по десятку и больше в день будет. Сотня в неделю.

Переворот производной — это локальный экстремум: локальный минимум или максимум. Ну и ворота для значений и индексов используй - насколько значение (или индекс) нового экстремума от текущего будет отличатся чтобы новое значение текущим стало - азы теории управления.
Единственный косяк может возникнуть - если измеряемая величина - монотонная функция, но в это слабо верится.

Если не хочешь с производными заморачиваться - используй значение и номер отчета, как Татарин предлагает.

Если концентрация газа часто падает до 0, можно взять два скользящих средних, один с большим, другой с меньшим шагом. Среднее с большим шагом будет соответствовать R0, с меньшим R.

PSS>> Храним минимум и время.
Balancer> Нет единого времени.

Добавить его. В еще одну переменную. Есть же у считывания данных определенный период.

Татарин> Ты совсем не хранишь отсчёты?

Конечно. Потому и тема, как считать статистику без хранения данных

Татарин> Да, стек минимумов, стек максимумов.

Только не стек, а очередь

Balancer> Конечно. Потому и тема, как считать статистику без хранения данных
Я так понял ты на ESP платах делаешь? Имея сколько там, 50 кБ ОЗУ и несколько мегабит SPI flash, жаловаться что памяти нет?!!

GOGI> Я так понял ты на ESP платах делаешь?

Не только. Например, данные у меня собирает Arduino Nano (банально т.к. в ESP только один канал АЦП), а ESP только ретранслирует. А возможен вариант с ретрансляцией по nRF24L01. И «вычисления» статистики на MQTT-хуках.

GOGI> и несколько мегабит SPI flash

Ресурс по циклам записи у ESP не так велик, там тысяч 10 циклов. Если каждые 10 секунд обновляться, то чуть больше, чем через сутки ресурс кончится Но, да, оперативки свободной килобайт до 10 можно, наверное, выкроить Но это — частный случай.