Nombre d'operations et temps de calcul

Question

Bonjour à tous et à toutes,


Je suis en train d'écrire des algorithmes en vue d'optimiser le temps de calcul et le nombre d'operation.
Dans un de mes cas, en gros, je dois calculer la moyenne d'une série puis son écart-type (simple) mais j'ai deux voies possibles :


La premiere :

> temporaire=0
> For i=1 to n
>      temporaire=temporaire+x(i)
> Next i
> moyenne=temporaire/n
> temporaire=0
> for i=1 to n
>       temporaire=temporaire+(x(i)-moyenne)^2
> Next i
> sigma=(temporaire/(n-1))^0.5


J'ai calculé la moyenne et l'écart-type des xi en 2*n+2 opérations avec deux boucles.


Mais si n est suffisamment grand (c'est-à-dire 1/n à peu près égal à 1/(n-1)) je peux utiliser une astuce en introduisant la valeur rms. J'ai alors une autre possibilité :

> temporaire1=0
> temporaire2=0
> For i=1 to n
>        temporaire1=temporaire1+x(i)
>        temporaire2=temporaire2+x(i)^2
> Next i
> moyenne=temporaire1/n
> rms2=temporaire2/n
> sigma=(rms2-moyenne^2)^0.5


J'ai aussi calculé la moyenne et l'écart-type des xi, mais cette fois-ci en 2*n+3 opérations en une seule boucle.


D'après vous, laquelle des deux prendra le plus de temps ?


Je vous remercie d'avance.
Cordialement,
Thomas.








Marin Marais

cs_Jack · Answer

Bon, bah on fait comme on a dit, hein ! Bonjour lol, désolé, dépassé par les stats Côté programmation : - Tu peux chronométrer chacune des méthodes en utilisant l'API GetTickCount qui te renverra le nombre de mSec écoulées depuis minuit et en faisant la différence entre la valeur mémorisée avant le calcul et la valeur après calcul Declare Function GetTickCount Lib "kernel32" Alias "GetTickCount" () As Long Dim mSecDepuisMinuit = GetTickCount Pour des calculs plus précis (si le temps de calculs est trop faible par rapport à la mSec), il y a d'autres méthodes pour récupérer le nombre de cycle d'horloge du processeur - précision au millionnième - Tu peux aussi essayer de remplacer les boucles For-Next par des Do-Loop, c'est quelques fois plus rapide : i = 0 Do While i < n ' tes calculs ici i = i + 1 Loop Vala Jack, MVP VB NB : Je ne répondrai pas aux messages privés

Le savoir est la seule matière qui s'accroit quand on la partage (Socrate)

NHenry · Answer

Bonjour

Tu peux aller voir ce tutorial.

Sinon, sache que x^2 est plus long à calculer que x*x.

Dans Word, j'Excel. (juste pour la citation)
VB (6, .NET1&2), C++, C#.Net1
Mon site

Renfield · Answer

pas GetTickCount !
GetProcessTimes....

sinon, tu hérite de tout ce qui tourne sur ta bécane dans les vlaeurs récupérees

Renfield
Admin CodeS-SourceS- MVP Visual Basic

marinmarais · Answer

Merci à vous trois pour le temps que vous avez consacré à mon problème.
Grâce à la fonction "TIC TOC" sur MatLab, j'ai pu regarder le temps nécessaire à ce calcul des deux manières.
J'ai généré des vecteurs aléatoires de 1000 lignes à partir desquels j'ai calculé la moyenne et l'écart-type suivant les deux algos.


J'ai mesuré 20 fois le temps dans chacun des deux cas et voici les temps moyens :
- 1er cas : 0.060s à +/- 0.007s près
- 2nd cas : 0.015s à +/- 0.003s près


Voili voilou.
Bien sûr le résultat ne serait pas tout à fait pareil sur VB mais j'ai l'intuition que la tendance serait la même.



A+,
Tom.

Marin Marais

Nombre d'operations et temps de calcul

4 réponses

Votre réponse

Discussions similaires