Есть датчик, этот датчик каждую секунду (или 1/1000 секунду) выдает некое значение мне нужно получить определенный интеграл (площадь, или среднее) за последнее время например за последний час, или за неделю.

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

пока на ум приходят 2 варианта
1. Что-то типа дерева и поиск типа как индексы
2. Подгонка под известные кривые и потом расчет интеграла

какие еще могут быть варианты?

>>например за последний час, или за неделю

Так интервал фиксированный?

ну я-бы сказал, что мне нужны значения примерно так, пока точно не знаю, но примерно так
за последние 10 мин
за последний час
за предпоследний час
за последние сутки
за предпоследние сутки

(2) простейшая математика же
если знаешь частоту выдачи значений и она фиксированная то даже кол-во значений для каждого
"за последние 10 мин
за последний час
за предпоследний час
за последние сутки
за предпоследние сутки"
хранить не надо для получения среднего арифметического

(a1+a2+..+an)/n

далее логично что средн(an_ср, an+1) = (an_ср*n + an+1)/n
короче накопительный счетчик среднего и кол-во значений храни и все

(3) * сорри ошибся в формуле делить надо на n+1

для интеграла или площади чуть сложней математика но почти всегда тоже можно

Делим всё виды интервалов и лимит сколько штук их храним, например:
Миллисекунды - 10000
Секунды - 6000
Минуты - 6000
...
Сутки - вечно

Снимаем значения минимальных единиц. Когда их становится больше лимита, удаляем часть и превращаем в следующую единицу как среднее. Когда тех будет больше лимита, аналогично в следующую.
Чем дальше делаем интервал, тем грубее картинка получается

(5) интеграл здесь и есть суммы, т.к. величины в общем то дискретные

(3) так ты получил среднее за (n+1), а нужно среднее за n, т.е. на интервале [2..(n+1)]

(8) я сначала получил среднее за n и сохранил его, а затем добавляю и получаю среднее n+1 и т.д.
т.е. всего пара значений хранится последнее среднее и кол-во n

(9)+ согласен что проблема что интервалы фиксированные а не скользящие
т.е. "последние 10 минут" на самом деле не последние (с учетом что сейчас идет 11 минута например) а "последний интервал в 10 минут"
а следующие 10 минут надо заново считать и главное хранить

(9)(10) ты тупо считаешь среднее за все время, а нужно именно среднее скользящее за фиксированный интервал

(11) скользящее никак не выйдет без хранения кучи значений

(12) готов это доказать? Я пока не уверен даже для точных значений. Аппроксимацию можно взять, например
S[2..(n+1)] ~ S[1..n]*(n-1)/n + a[n+1]/n

паучок portia решает подобные задачи постоянно.

достаточно хранить средний интегральный показатель X(n) за предыдущий период  и количество измерений N за этот период. уточнение интегрального показателя при (N+1)-ом измерении показателя равном X средний интегральный показатель стане равен:
X(n+1) = ( X(n) * N + X ) / ( N + 1 )
-- и этот новый набор показателей (новые значения среднего интегрального значения и количесто измерений) - гомоморфен предыдущему, т.е. дат возможность таким же алгоритмом вычислять правильное значение этого показателя на любом шаге.

(15) Точно можно же вычитать ненужное значение устаревшее значение, если его отдельно сохранить.
Короче храним первое значение, "средний интегральный показатель" и кол-во измерений

(16)+ хотя не прокатит, следующее значение для вычитания где взять, если оно уже усреднено

(0) Ответ очевиден, ты на него сам почти ответил в вопросе. Если не хватает памяти чтобы посчитать точное значение, то считай неточное, на сколько хватает памяти.
Сколько максимально значений ты можешь хранить в памяти? Вот столько и храни. N последних, либо весь необходимый период разбиваешь на N частей, для каждой считаешь среднее значение, и их хранишь.

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

вместо 10 значений храни их среднее

те раз в минуту усредняй, раз в 10 мин, раз в час, сутки

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

На сколько я понимаю самым правильным будет (6)
Как альтернативу наверно можно рассмотреть сплайны, например считаем среднее. При добавлении нового значения, Сначало из среднего вычитаем последнее (расчитанное как среднее) и потом добавляем новое. Для этого нужно хранить сумму элементов и их количество, ну или сумму квадратов значений. Надо в екселе попробовать...

Можно ещё не абсолютные значения, а дельты хранить. Они места меньше занимают.

А вообще, эта задача давно и эффективно решена в потоковом кодировании аудио и видео.

посчитал в екселе, для моих данных разницы между (6) и (23) практически нет, отклонения менее 1%

то есть мне на каждый интервал нужно хранить всего 3 величины

1. сумму всех измерений в этом диапазоне
2. количество измерений в диапазоне
3. среднее в диапазоне

для всех диапазонов которые "текущие" этого более чем достаточно, но для диапазонов типа "вчера" придется что-то еще придумывать, типа хранить "за два дня" и вычитать "сегодня"

(26) умничко

Посмотрите RRDTool - она как раз под эту задачу и сделана.
Хранение средних значений за указанный интервал. При добавлении очередного значения пересчитывается хранящееся среднее, куда оно попадает.
Трендов (рядов хранения) может быть несколько, каждая со своим интервалом.

Я в ней когда-то давно хранил и визуализировал температуру.
Было 4 графика. Суточный, недельный, месячный и годовой. Рабочая область формируемой картинки с графиком вроде составляла 720 пикселей по горизонтали.
Т.е. в суточном графике разрешение одного пикселя составляло 120 секунд, недельном - 14 минут, месячном - 1 час и годовом - ок. 30 часов. Точно также хранилось и в базе - среднее за 120 сек, за 14 минут и т.д. Хотя масштаб картинок и базы можно сделать разным.
Пересчитывалось все само при сохранении в базе нового значения, для которого указывались его дата/время.

(28) :) мне все это хозяйство нужно уместить в 2 (ну или максимум в 8) килобайта оперативки (включая все переменные кода)

(30) как я понимаю логгирование температуры. А какова цель интегрирования ? Сам просто немного тем же занимаюсь

(0) Мэтр, вот тут известный в ардуино-сообществах товарищ как раз изложил варианты: https://alexgyver.ru/lessons/filters/
Там есть как раз "Бегущее среднее арифметическое" и "Экспоненциальное бегущее среднее". Очень похоже на желаемое

(2) Ну так и храни значения в пределах минимальных тебе ограничений+ детализацию до минимальных значений