Calcul de la moyenne mobile en C ++

J’essaie de calculer la moyenne mobile d’un signal. La valeur du signal (un double) est mise à jour à des moments aléatoires. Je cherche un moyen efficace de calculer sa moyenne pondérée dans le temps sur une fenêtre temporelle, en temps réel. Je pourrais le faire moi-même, mais c’est plus difficile que je ne le pensais.

La plupart des ressources que j’ai trouvées sur Internet calculent la moyenne mobile du signal périodique, mais la mienne est mise à jour à un moment aléatoire.

Est-ce que quelqu’un connaît de bonnes ressources pour cela?

Merci

L’astuce est la suivante: Vous obtenez des mises à jour à des moments aléatoires via void update(int time, float value) . Cependant, vous devez également suivre quand une mise à jour tombe en dehors de la fenêtre de temps. Vous devez donc définir une “alarme” qui appelle à l’ time + N ce qui empêche la mise à jour précédente d’être prise en compte dans le calcul.

Si cela se produit en temps réel, vous pouvez demander au système d’exploitation d’appeler une méthode void drop_off_oldest_update(int time) à appeler à l’ time + N

S’il s’agit d’une simulation, vous ne pouvez pas obtenir d’aide du système d’exploitation et vous devez le faire manuellement. Dans une simulation, vous appelez des méthodes avec le temps fourni comme argument (ce qui ne correspond pas au temps réel). Cependant, une hypothèse raisonnable est qu’il est garanti que les appels sont tels que les arguments de temps augmentent. Dans ce cas, vous devez conserver une liste sortingée des valeurs de l’heure de l’alarme. Pour chaque appel de update et de read vérifiez si l’argument de l’heure est supérieur à l’en-tête de la liste des alarmes. Même s’il est supérieur, vous effectuez le traitement lié à l’alarme (déposez la mise à jour la plus ancienne), retirez la tête et vérifiez à nouveau jusqu’à ce que toutes les alarmes précédant l’heure indiquée soient traitées. Ensuite, faites l’appel de mise à jour.

Jusqu’ici, j’ai supposé que ce que vous feriez pour le calcul réel est évident, mais je vais élaborer au cas où. Je suppose que vous avez une méthode float read (int time) que vous utilisez pour lire les valeurs. Le but est de rendre cet appel aussi efficace que possible. Donc, vous ne calculez pas la moyenne mobile chaque fois que la méthode de read est appelée. Au lieu de cela, vous calculez la valeur à partir de la dernière mise à jour ou de la dernière alarme et modifiez cette valeur par quelques opérations à virgule flottante pour tenir compte du temps écoulé depuis la dernière mise à jour. (c’est-à-dire un nombre constant d’opérations, sauf peut-être le traitement d’une liste d’alarmes empilées).

Espérons que cela soit clair – il devrait s’agir d’un algorithme assez simple et très efficace.

Optimisation supplémentaire : un des problèmes restants est qu’un grand nombre de mises à jour se produisent dans la fenêtre de temps, puis il y a une longue période pour laquelle il n’ya ni lecture ni mise à jour, puis une lecture ou une mise à jour se produit. Dans ce cas, l’algorithme ci-dessus sera inefficace pour mettre à jour de manière incrémentielle la valeur pour chacune des mises à jour en train de tomber. Cela n’est pas nécessaire car nous nous intéressons uniquement à la dernière mise à jour au-delà de la fenêtre de temps; donc, s’il était possible de déposer efficacement toutes les mises à jour anciennes, cela aiderait.

Pour ce faire, nous pouvons modifier l’algorithme afin d’effectuer une recherche binary des mises à jour afin de trouver la mise à jour la plus récente avant la fenêtre temporelle. Si relativement peu de mises à jour doivent être “supprimées”, il est possible de mettre à jour de manière incrémentielle la valeur de chaque mise à jour supprimée. Mais si de nombreuses mises à jour doivent être supprimées, il est alors possible de recalculer la valeur à partir de zéro après avoir supprimé les anciennes mises à jour.

Annexe sur le calcul incrémental: Je devrais préciser ce que je veux dire par calcul incrémental ci-dessus dans la phrase “ajuster” cette valeur par quelques opérations en virgule flottante pour tenir compte du temps écoulé depuis la dernière mise à jour . Calcul initial non incrémental :

Commencer avec

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

puis parcourez les mises à jour relevant_updates par ordre croissant de temps:

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

et enfin

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

Maintenant, si exactement une mise à jour tombe de la fenêtre mais qu’aucune nouvelle mise à jour n’arrive, ajustez sum comme sum :

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

(notez qu’il s’agit de prior_update' dont l’horodatage est modifié pour le début du dernier début de fenêtre). Et si exactement une mise à jour entre dans la fenêtre, mais qu’aucune nouvelle mise à jour ne tombe, ajustez sum comme sum :

 sum += previously_most_recent_update.value * corresponding_time_to_next_update.

Comme cela devrait être évident, il s’agit d’une ébauche approximative, mais nous espérons que cela montre comment vous pouvez maintenir la moyenne, de sorte qu’il s’agit de 0 (1) opération par mise à jour sur une base amortie. Mais notez l’optimisation supplémentaire dans le paragraphe précédent. Notez également les problèmes de stabilité évoqués dans une réponse plus ancienne, ce qui signifie que les erreurs en virgule flottante peuvent s’accumuler lors d’un grand nombre d’opérations incrémentielles, de sorte qu’il existe une divergence par rapport au résultat du calcul complet qui est significative pour l’application.

Si une approximation est correcte et qu’il y a un minimum de temps entre les échantillons, vous pouvez essayer le super-échantillonnage. Ayez un tableau qui représente des intervalles de temps régulièrement espacés plus courts que le minimum et stockez à chaque période le dernier échantillon reçu. Plus l’intervalle est court, plus la moyenne sera proche de la vraie valeur. La période ne doit pas dépasser la moitié du minimum, sinon il y a une chance de rater un échantillon.

 #include  #include  // Sample - the type of a single sample // Date - the type of a time notation // DateDiff - the type of difference of two Dates template  class TWMA { private: typedef std::map 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 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 }

Note: Apparemment, ce n’est pas la façon d’aborder cela. Laissez-le ici pour référence sur ce qui ne va pas avec cette approche. Vérifiez les commentaires.

MISE À JOUR – basé sur le commentaire d’Oli … pas sûr de l’instabilité dont il parle cependant.

Utilisez une carte sortingée des “heures d’arrivée” en fonction des valeurs. À l’arrivée d’une valeur, ajoutez l’heure d’arrivée à la carte sortingée ainsi que sa valeur et mettez à jour la moyenne mobile.

avertissant qu’il s’agit d’un 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(); }

Là ... Pas complètement épanoui mais vous avez l’idée.

Choses à noter : Comme je l'ai dit ce qui précède est un pseudo code. Vous devrez choisir une carte appropriée. Ne supprimez pas les paires au fur et à mesure de votre parcours car vous invalideriez l’iterator et vous devrez recommencer.
Voir aussi le commentaire d'Oli ci-dessous.