Obliczanie średniej ruchomej w C++

Question

Próbuję obliczyć średnią ruchomą sygnału. Wartość sygnału (podwójna) jest aktualizowana losowo razy. Szukam skutecznego sposobu obliczenia jego średniej ważonej w czasie w oknie czasowym, w czasie rzeczywistym. Mógłbym to zrobić sam, ale jest to trudniejsze, niż myślałem.

Większość zasobów, które znalazłem w Internecie, oblicza średnią ruchomą okresowego sygnału, ale aktualizacje kopalni w losowym czasie.

Czy ktoś zna odpowiednie zasoby?

Dzięki

Answer 1

Sztuczka jest następująca: Otrzymujesz aktualizacje w losowych czasach poprzez void update(int time, float value). Jednak musisz również śledzić, kiedy aktualizacja wypadnie z okna czasowego, co oznacza, więc ustawiasz "alarm", który wywołał na time + N, który usuwa aktualizację poprzednią od kiedykolwiek rozważaną ponownie w obliczeniach.

Jeśli to dzieje się w czasie rzeczywistym, można zwrócić się do systemu operacyjnego, aby nawiązać połączenie ze sposobem void drop_off_oldest_update(int time) być nazywany w time + N

Jeśli jest to symulacja, nie można uzyskać pomoc z systemu operacyjnego i trzeba to zrobić ręcznie. W symulacji można wywołać metody z czasem podanym jako argument (który nie koreluje z czasem rzeczywistym). Jednak rozsądnym założeniem jest to, że połączenia są gwarantowane tak, że argumenty czasu rosną. W takim przypadku musisz zachować posortowaną listę wartości czasu alarmu, a dla każdego połączenia update i read sprawdzić, czy argument czasu jest większy niż nagłówek listy alarmów.Podczas gdy jest on większy, wykonujesz przetwarzanie związane z alarmem (usuwając najstarszą aktualizację), usuń głowicę i sprawdź ponownie, aż wszystkie alarmy przed danym czasem zostaną przetworzone. Następnie wykonaj wywołanie aktualizacji.

Do tej pory zakładałem, że jest oczywiste, co zrobiłbyś dla rzeczywistych obliczeń, ale rozwiążę je na wszelki wypadek. Zakładam, że masz metodę float read (int time), której używasz do odczytu wartości. Celem jest uczynienie tego połączenia tak efektywnym, jak to tylko możliwe. Więc obliczasz średnią ruchomą za każdym razem, gdy wywoływana jest metoda read. Zamiast tego należy wstępnie obliczyć wartość z ostatniej aktualizacji lub ostatniego alarmu i "poprawić" tę wartość przez kilka operacji zmiennoprzecinkowych, aby uwzględnić upływ czasu od ostatniej aktualizacji. (i. e. stałą liczbę operacji, z wyjątkiem prawdopodobnie przetwarzania listy alarmów ułożonych w stos).

Mam nadzieję, że jest to jasne - powinien to być dość prosty algorytm i dość wydajny.

Dalsza optymalizacja: jeden z pozostałych problemów jest jeśli duża liczba aktualizacji zdarzyć w oknie czasowym, to nie jest to długi czas, dla których nie są ani czyta ani aktualizacje, a następnie odczytu lub zmiana przychodzi . W takim przypadku powyższy algorytm będzie nieskuteczny przy stopniowej aktualizacji wartości każdej z aktualizacji, która spada. Nie jest to konieczne, ponieważ dbamy tylko o ostatnią aktualizację poza przedziałem czasowym, więc jeśli istnieje sposób, aby skutecznie usunąć wszystkie starsze aktualizacje, pomogłoby to.

Aby to zrobić, możemy zmodyfikować algorytm do binarnego wyszukiwania aktualizacji, aby znaleźć najnowszą aktualizację przed upływem okna czasowego. Jeśli istnieje stosunkowo niewiele aktualizacji, które należy "upuścić", wówczas można aktualizować przyrostowo wartość dla każdej usuniętej aktualizacji. Ale jeśli istnieje wiele aktualizacji, które należy usunąć, można ponownie obliczać wartość od zera po usunięciu starych aktualizacji.

Dodatek bieżących obliczeń: powinienem wyjaśnić, co mam na myśli bieżących obliczeń powyżej w zdaniu „dostrojenia” tę wartość przez kilka operacji zmiennoprzecinkowych, aby uwzględnić upływ czasu od ostatniej aktualizacji. Początkowa bez przyrostowego Obliczenia:

Rozpocznij

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 */, 

następnie iteracyjnego relevant_updates w kolejności od czasu:

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

i wreszcie

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

Teraz, jeśli dokładnie jedna zmiana spada z okna, ale żadne nowe aktualizacje przybyć dostosować sum jak:

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

(pamiętać, że jest prior_update' która jego timestamp zmodyfikowany zacząć od ostatniego okna rozpoczynającego). A jeśli dokładnie jedna zmiana wejdzie przez okno, lecz żadne nowe aktualizacje odpadać, wyregulować sum jak:

sum += previously_most_recent_update.value * corresponding_time_to_next_update. 

Jak powinno być oczywiste, to jest szorstki szkic, ale mam nadzieję, że to pokazuje, w jaki sposób można utrzymać średnią tak, że jest O (1) operacje na aktualizację według zamortyzowanego kosztu. Ale zanotuj dalszą optymalizację w poprzednim paragrafie.Należy również zwrócić uwagę na problemy związane ze stabilnością, do których nawiązuje starsza odpowiedź, co oznacza, że ​​błędy zmiennoprzecinkowe mogą kumulować się w dużej liczbie takich operacji przyrostowych, tak że istnieje rozbieżność w wyniku pełnego obliczenia, który jest istotny dla aplikacji.

Answer 2

Uwaga: Widocznie to nie jest sposób podejścia do tego. Pozostawiając to tutaj dla odniesienia, co jest nie tak z tym podejściem. Sprawdź komentarze.

ZAKTUALIZOWANA - na podstawie komentarza Oli ... nie jest jednak pewna niestabilności, o której mówi.

Użyj posortowanej mapy "czasów przybycia" względem wartości. Po nadejściu wartości dodaj czas przybycia do posortowanej mapy wraz z jej wartością i zaktualizuj średnią ruchomą.

ostrzeżenie to jest pseudo-code:

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(); 
} 

Nie ... Nie w pełni uregulowana, ale masz pomysł.

Rzeczy do zapamiętania: Jak już powiedziałem, powyższy kod to pseudo kod. Musisz wybrać odpowiednią mapę. Nie usuwaj par podczas wykonywania iteracji, ponieważ spowoduje to unieważnienie iteratora i będzie konieczne ponowne uruchomienie.
Zobacz poniżej komentarz Oli.

Answer 3

Jeśli przybliżenie jest prawidłowe, a między próbkami jest minimalny czas, można spróbować wykonać superpróbkowanie. Posiadaj tablicę, która reprezentuje równomiernie rozmieszczone interwały czasowe, które są krótsze niż minimum, i dla każdego okresu przechowuj najnowszą próbkę, która została odebrana. Im krótszy przedział czasu, tym bliżej wartości średniej do rzeczywistej. Okres nie powinien być większy niż połowa minimum lub istnieje szansa na brak próbki.

Answer 4

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