Вычисление скользящей средней в С++

Ответ 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. Вместо этого вы прекомпретируете значение с последнего обновления или последнего аварийного сигнала и "настроите" это значение на пару операций с плавающей запятой, чтобы учитывать течение времени с момента последнего обновления. (то есть постоянное количество операций, за исключением, возможно, обработки списка сложенных аварийных сигналов).

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

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

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

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

начните с

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) операции для каждого обновления на амортизированной основе. Но обратите внимание на дальнейшую оптимизацию в предыдущем параграфе. Также обратите внимание на проблемы стабильности, упомянутые в более старом ответе, что означает, что ошибки с плавающей запятой могут накапливаться на большом количестве таких дополнительных операций, так что существует расхождение с результатом полного вычисления, значимого для приложения.

Ответ 2

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

Ответ 3

#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
}

Ответ 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();
}

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

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