Расчет скользящего среднего в C ++

Question

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

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

Кто-нибудь знает хорошие ресурсы для этого?

Спасибо

Answer 1

Хитрость в следующем: вы получаете обновления в случайное время через void update(int time, float value).Однако вам также необходимо отслеживать, когда обновление падает временного окна, поэтому вы устанавливаете «будильник», который вызывается на time + N, который удаляет предыдущее обновление из когда-либо рассмотренных.снова в вычислении.

Если это происходит в режиме реального времени, вы можете запросить у операционной системы вызов метода void drop_off_oldest_update(int time) для вызова на time + N

Если этосимуляция, вы не можете получить помощь от операционной системы, и вам нужно сделать это вручную.В симуляции вы вызываете методы с указанным в качестве аргумента временем (которое не коррелирует с реальным временем).Тем не менее, разумным предположением является то, что вызовы гарантированно будут такими, что время аргументов увеличивается.В этом случае вам нужно вести отсортированный список значений времени будильника, и для каждого вызова update и read вы проверяете, превышает ли аргумент времени заголовок списка тревог.Хотя это больше, вы выполняете обработку, связанную с аварийными сигналами (отбрасываете самое старое обновление), снимите головку и проверяйте снова, пока все аварийные сигналы до заданного времени не будут обработаны.Затем выполните вызов обновления.

До сих пор я предполагал, что очевидно, что вы будете делать для реальных вычислений, но я подробно остановлюсь на всякий случай.Я предполагаю, что у вас есть метод float read (int time), который вы используете для чтения значений.Цель состоит в том, чтобы сделать этот призыв максимально эффективным.Таким образом, вы не вычисляете скользящее среднее значение каждый раз, когда вызывается метод read.Вместо этого вы предварительно вычисляете значение с момента последнего обновления или последнего аварийного сигнала и «настраиваете» это значение с помощью нескольких операций с плавающей запятой, чтобы учесть время, прошедшее с момента последнего обновления.(т. е. постоянное количество операций, за исключением, возможно, обработки списка накопленных аварий).

Надеюсь, это понятно - это должен быть довольно простой алгоритм и довольно эффективный.

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

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

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

начинаются с

sum = 0; 
updates_in_window = /* set of all updates within window */; 
prior_update' = /* most recent update prior to window with timestamp tweaked to window beginning */; 
relevant_updates = /* union of prior_update' and updates_in_window */,  

, затем итерируются по relevant_updates в порядке увеличения времени:

for each update EXCEPT last { 
    sum += update.value * time_to_next_update; 
},  

и наконец

moving_average = (sum + last_update * time_since_last_update) / window_length;.

Теперь, если ровно одно обновление выпадает из окна, но новые обновления не поступают, настройте sum как:

sum -= prior_update'.value * time_to_next_update + first_update_in_last_window.value * time_from_first_update_to_new_window_beginning;

(обратите внимание, что prior_update' имеет метку времени, измененную для запускапоследнего начала окна).И если в окно входит ровно одно обновление, но новые обновления не отваливаются, настройте sum как:

sum += previously_most_recent_update.value * corresponding_time_to_next_update. 

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

Answer 2

#include <map>
#include <iostream>

// Sample - the type of a single sample
// Date - the type of a time notation
// DateDiff - the type of difference of two Dates    
template <class Sample, class Date, class DateDiff = Date>
class TWMA {
private:
  typedef std::map<Date, Sample> qType;
  const DateDiff windowSize; // The time width of the sampling window
  qType samples; // A set of sample/date pairs
  Sample average; // The answer

public:

  // windowSize - The time width of the sampling window
  TWMA(const DateDiff& windowSize) : windowSize(windowSize), average(0) {}

  // Call this each time you receive a sample
  void
  Update(const Sample& sample, const Date& now) {
    // First throw away all old data
    Date then(now - windowSize);
    samples.erase(samples.begin(), samples.upper_bound(then));

    // Next add new data
    samples[now] = sample;

    // Compute average: note: this could move to Average(), depending upon
    // precise user requirements.
    Sample sum = Sample();
    for(typename qType::iterator it = samples.begin();
        it != samples.end();
        ++it) {
      DateDiff duration(it->first - then);
      sum += duration * it->second;
      then = it->first;
    }
    average = sum / windowSize;
  }

  // Call this when you need the answer.
  const Sample& Average() { return average; }

};

int main () {
  TWMA<double, int> samples(10);

  samples.Update(1, 1);
  std::cout << samples.Average() << "\n"; // 1
  samples.Update(1, 2);
  std::cout << samples.Average() << "\n"; // 1
  samples.Update(1, 3);
  std::cout << samples.Average() << "\n"; // 1
  samples.Update(10, 20);
  std::cout << samples.Average() << "\n"; // 10
  samples.Update(0, 25);
  std::cout << samples.Average() << "\n"; // 5
  samples.Update(0, 30);
  std::cout << samples.Average() << "\n"; // 0
}

Answer 3

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

Answer 4

Примечание: Видимо, это не тот подход Оставляя это здесь для справки о том, что не так с этим подходом. Проверьте комментарии.

ОБНОВЛЕНО - на основании комментария Оли ... хотя и не уверен в нестабильности, о которой он говорит.

Использовать отсортированную карту «времени прибытия» против значений. По прибытии значения добавьте время прибытия к отсортированной карте вместе с ее значением и обновите скользящее среднее.

предупреждение, что это псевдокод:

SortedMapType< int, double > timeValueMap;

void onArrival(double value)
{
    timeValueMap.insert( (int)time(NULL), value);
}

//for example this runs every 10 seconds and the moving window is 120 seconds long
void recalcRunningAverage()
{
    // you know that the oldest thing in the list is 
    // going to be 129.9999 seconds old
    int expireTime = (int)time(NULL) - 120;
    int removeFromTotal = 0;
    MapIterType i;
    for( i = timeValueMap.begin();
    (i->first < expireTime || i != end) ; ++i )
    {
    }

    // NOW REMOVE PAIRS TO LEFT OF i

    // Below needs to apply your time-weighting to the remaining values
    runningTotal = calculateRunningTotal(timeValueMap); 
    average = runningTotal/timeValueMap.size();
}

Там ... Не полностью реализовано, но вы поняли.

На заметку : Как я уже сказал выше, это псевдокод. Вам нужно будет выбрать подходящую карту. Не удаляйте пары во время итерации, так как вы сделаете недействительным итератор и вам придется начинать заново.
Смотрите также комментарий Оли ниже.