Cálculo de la media móvil en C++

Question

Estoy tratando de calcular la media móvil de una señal. El valor de la señal (un doble) se actualiza en momentos aleatorios. Estoy buscando una forma eficiente de calcular su promedio ponderado de tiempo en una ventana de tiempo, en tiempo real. Podría hacerlo solo, pero es más desafiante de lo que pensaba.

La mayoría de los recursos que he encontrado en Internet están calculando el promedio móvil de la señal periódica, pero las actualizaciones de la mina en tiempo aleatorio.

¿Alguien sabe buenos recursos para eso?

Gracias

Answer 1

El truco es el siguiente: Recibe actualizaciones en momentos aleatorios a través de void update(int time, float value). Sin embargo, también es necesario que también realice un seguimiento cuando una actualización caiga la ventana de tiempo, por lo que establece una "alarma" que llamó al time + N que elimina la anterior actualización que nunca se considerará nuevamente en el cálculo.

Si esto ocurre en tiempo real, puede solicitar que el sistema operativo para realizar una llamada a un método void drop_off_oldest_update(int time) ser llamado a time + N

Si esto es una simulación, no se puede obtener ayuda del sistema operativo y se necesito hacerlo manualmente En una simulación, llamaría a los métodos con el tiempo suministrado como argumento (que no se correlaciona con el tiempo real). Sin embargo, una suposición razonable es que las llamadas están garantizadas de tal manera que los argumentos de tiempo están aumentando. En este caso, necesita mantener una lista ordenada de valores de tiempo de alarma, y ​​para cada llamada update y read, compruebe si el argumento de tiempo es mayor que el encabezado de la lista de alarmas.Si bien es mayor, usted realiza el procesamiento relacionado con la alarma (deje la actualización más antigua), retire el cabezal y vuelva a verificar hasta que se procesen todas las alarmas anteriores al tiempo determinado. Luego haz la llamada de actualización.

Hasta ahora he supuesto que es obvio lo que harías para el cálculo real, pero lo elaboraré por las dudas. Supongo que tiene un método float read (int time) que usa para leer los valores. El objetivo es hacer que esta llamada sea lo más eficiente posible. Por lo tanto, haga no calcule el promedio móvil cada vez que se llame al método read. En su lugar, calcula previamente el valor a partir de la última actualización o la última alarma, y ​​"ajusta" este valor mediante un par de operaciones de punto flotante para tener en cuenta el paso del tiempo desde la última actualización. (Es decir, un número constante de operaciones, excepto tal vez para procesar una lista de alarmas acumuladas).

Afortunadamente esto es claro, este debería ser un algoritmo bastante simple y bastante eficiente.

Optimización adicional: uno de los problemas restantes es que si se produce una gran cantidad de actualizaciones dentro de la ventana de tiempo, hay un tiempo largo para el que no hay ni actualizaciones ni actualizaciones, y luego aparece una lectura o actualización . En este caso, el algoritmo anterior será ineficaz para actualizar incrementalmente el valor de cada una de las actualizaciones que se está cayendo. Esto no es necesario porque solo nos preocupa la última actualización más allá de la ventana de tiempo, por lo que si hay una forma de dejar de forma eficiente todas las actualizaciones anteriores, sería útil.

Para hacer esto, podemos modificar el algoritmo para hacer una búsqueda binaria de actualizaciones para encontrar la actualización más reciente antes de la ventana de tiempo. Si hay relativamente pocas actualizaciones que se deben "descartar", entonces se puede actualizar incrementalmente el valor de cada actualización eliminada. Pero si hay muchas actualizaciones que se deben descartar, se puede volver a calcular el valor desde cero después de dejar las actualizaciones anteriores.

Apéndice sobre incremental Cálculo: que debe aclarar lo que quiero decir por el cómputo incremental de más arriba en la sentencia "ajustar" este valor por un par de operaciones de punto flotante para dar cuenta del paso del tiempo desde la última actualización. inicial no incremental cálculo:

comienzo con

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

continuación, iterar sobre relevant_updates con el fin de aumentar el tiempo:

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

y finalmente

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

Ahora bien, si exactamente una actualización cae de la ventana, pero no hay nuevas actualizaciones llegan, ajustar sum como:

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

(tenga en cuenta que es prior_update' que tiene su marca de tiempo modificado al inicio de la última ventana de inicio). Y si exactamente una actualización entra en la ventana, pero no hay nuevas actualizaciones se caen, ajuste sum como:

sum += previously_most_recent_update.value * corresponding_time_to_next_update. 

Como debería ser obvio, esto es un boceto pero esperemos que muestra cómo se puede mantener el promedio tal que es O (1) operaciones por actualización sobre una base amortizada. Pero tenga en cuenta una mayor optimización en el párrafo anterior.También tenga en cuenta los problemas de estabilidad aludidos en una respuesta anterior, lo que significa que los errores de punto flotante pueden acumularse en un gran número de tales operaciones incrementales de modo que haya una divergencia con respecto al resultado del cómputo completo que es significativo para la aplicación.

Answer 2

Nota: Al parecer esta no es la manera de abordar esto. Dejándolo aquí para referencia sobre lo que está mal con este enfoque. Verifica los comentarios.

ACTUALIZADO - basado en el comentario de Oli ... no estoy seguro acerca de la inestabilidad de la que está hablando.

Utilice un mapa ordenado de "tiempos de llegada" contra los valores. Al llegar un valor, agregue el tiempo de llegada al mapa ordenado junto con su valor y actualice el promedio móvil.

ADVERTENCIA Este es pseudo-código:

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

No ... No plasmen plenamente pero se entiende la idea.

Puntos a tener en cuenta: Como dije, lo anterior es un pseudo código. Tendrás que elegir un mapa apropiado. No elimine los pares mientras itera, ya que invalidará el iterador y tendrá que volver a comenzar.
Véase también el comentario de Oli a continuación.

Answer 3

Si la aproximación es correcta y existe un tiempo mínimo entre las muestras, puede probar el supermuestreo. Tenga una matriz que represente intervalos de tiempo espaciados uniformemente que sean más cortos que el mínimo, y en cada período de tiempo almacene la última muestra que se recibió. Cuanto más corto sea el intervalo, más cerca estará el promedio del valor verdadero. El período no debe ser mayor a la mitad del mínimo o existe la posibilidad de perder una muestra.

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 
}