Optimisation de code

Version imprimable

Voir 40 message(s) de cette discussion en une page

04/04/2007, 12h34
vinzzzz

Oui en effet je pensais pas que faire:
ind3 = t_part[i]->nvar_mone ;

ca prendrais moins de temps que de mettre directement t_part[i]->nvar_mone .

Pour memmove, je suppose qu'on gagne du temps ...

En tout cas merci pr tous ces conseils ;)
04/04/2007, 12h41
vinzzzz

Pour tes deux derniers exemples, on gagnerai vraiment?
Parce que finalement si non prends ton premer exemple, on boucle toujours sur k, et on doit en plus incrémenter x0 , donc on ajoute quelques opérations non?
04/04/2007, 12h43
souviron34

Citation:

Envoyé par vinzzzz

Oui en effet je pensais pas que faire:
ind3 = t_part[i]->nvar_mone ;

ca prendrais moins de temps que de mettre directement t_part[i]->nvar_mone .

Pour memmove, je suppose qu'on gagne du temps ...

En tout cas merci pr tous ces conseils ;)

pour memmove tu gagnes énormément

Et pour le reste, tu gagnes peu, mais sur beaucoup tu gagnes beaucoup : à chaque fois, tu fais une somme (pour calculer l'adresse) au lieu d'avoir le chiffre déjà prêt...

Et c'est vrai pour chaque indice. Et pour l'élément du tableau :

Vaux mieux mettre :

tab[i] que tab[fonction(i)]
valtab que tab[i]

donc si tu fais référence à plusieurs fois le même élément tu le mets dans une variable, si tu fais référence à plusieurs fois le même indice tu le mets dans une variable intermédiaire..
04/04/2007, 12h54
souviron34
Citation:

Envoyé par vinzzzz

Pour tes deux derniers exemples, on gagnerai vraiment?
Parce que finalement si non prends ton premer exemple, on boucle toujours sur k, et on doit en plus incrémenter x0 , donc on ajoute quelques opérations non?

non

Quand tu fais :
Code:

1 2 3 for(k = t_part[i]->delay_pone ; k > 0 ; k--) { t_part[i]->x[j][k] = t_part[i]->x[j][k-1] ;
il faut calculer :

l'adresse t->part[i] : 1 somme (éventuellement *2 si pas flag optimisé)
l'adresse t->part[i]->x : 1 somme ( kif kif)
l'adresse t->part[i]->x[j] : 1 somme (kif kif)
l'adresse t->part[i]->x[j][k] : 1 somme
l'adresse t->part[i]->x[j][k-1] : 1 somme

donc entre 5 et 8 sommes

Alors que dans :
Code:

1 2 3 4 for(k = t_part[i]->delay_pone ; k > 0 ; k--) { *x0 = *(x0-1) ; x0= x0 - 1 ;
calculer x0 -1 : une somme
l'affecter : une copie ou une somme (dépendant de comment c'est optimisé)

Donc en net 2 sommes max.

Il n'y a que là ou je ne suis pas sûr si on gagnerais en faisant :

p = x0 -1
*x0 = *p
x0 = p ;

mais sans doute (la copie doit prendre moins de temps que la somme)
et dans ce cas on aurait (une somme + 2 copies)
04/04/2007, 12h56
Thierry Chappuis

Citation:

Envoyé par lun4t1k

Pour en revenir a la complexité, il me semble tout de même que le calcul de la complexité d'un while peut s'avérer plus difficile à calculer lors d'utilisations particulières dans des algos particuliers!

il existe un algo qui contient un while dont la complexité n'a pu etre déterminée, et je n'en connais pas avec un for! (je n'ai plus l'algo ne demandez pas! :P )

Tu as des exemples concrets... (parce que je vois pas à quel niveau il pourrait y avoir une quelconque différence)

Thierry
04/04/2007, 13h00
vinzzzz
Si j'ai bien compris, quand je fais:
Code:

1 2 3 4 5 6 for(j = 0 ; j < t_part[i]->nvar ; j++) { for(k = t_part[i]->delay_pone ; k > 0 ; k--) { t_part[i]->x[j][k] = t_part[i]->x[j][k-1] ; } }
Cette instruction:
t_part[i]->x[j][k]
va demander en fait a chaque fois un calcul pour obtenir t_part[i]->x[j], alors que j'aurais pu l'obtenir en une fois juste avant de rentrer dans la deuxième boucle?
Et de la même manière, puisque j'utilise beaucoup le pointeur qui se trouve a t_part[i], si je stocke t_part[i] dans une variable intemédiaire au tout début de la boucle principale, ca éviterait également des calculs pour le récupérer dans le tableau?

Hésite pas a me coriger si jsuis a coté de la plaque :)
04/04/2007, 13h03
vinzzzz

Ok donc y'a encore vraiment moyen d'améliorer tout ca... Merci pour toutes ces précisions.
04/04/2007, 13h06
souviron34

C'est pour ça que je me permettais de douter en te lisant...

Citation:

Envoyé par vinzzzz

...
Pour les autres optimisations, t'en fais pas je commence a avoir l'oeil pour éviter des calculs redondants ... ;)

;)
04/04/2007, 13h08
vinzzzz

L'ignorant qui s'ignore 8-) ;)

Mais ca fait d'autant plus plaisir d'en apprendre encore!
En fait tous ces calculs d'adresse avec les tableau, les pointeurs etc... intuitivement j'y ait pas pensé. Et ca explique je suppose pourquoi le parcours d'une liste chainée ca prends plus de temps que celui d'un tableau.
04/04/2007, 13h09
souviron34

Citation:

Envoyé par vinzzzz

Cette instruction:
t_part[i]->x[j][k]
va demander en fait a chaque fois un calcul pour obtenir t_part[i]->x[j], alors que j'aurais pu l'obtenir en une fois juste avant de rentrer dans la deuxième boucle?
Et de la même manière, puisque j'utilise beaucoup le pointeur qui se trouve a t_part[i], si je stocke t_part[i] dans une variable intemédiaire au tout début de la boucle principale, ca éviterait également des calculs pour le récupérer dans le tableau?

Absolument.... C'est le principe..

Après, comme on disait plus haut, il y a d'autres choses, les structures, les avantages du langage (comme le memmove) etc... mais là déjà, sans remettre en cause la structure du programme , déjà c'est nettement plus lisible, et ensuite on a optimisé le code "hors structure"..

Citation:

Envoyé par mujigka

Tu as des exemples concrets... (parce que je vois pas à quel niveau il pourrait y avoir une quelconque différence)

Thierry

Malheureusement , ce jour là je n'ai pas noté cet algorithme.
La seule chose que j'ai c'est que ca vient d'un prof d'algo. :roll:

La complexité de la boucle for est calculée par la complexité du corps de cette boucle multipliée par le nombre de fois qu’elle est répétée.
En règle générale, pour déterminer la complexité d’une boucle while, il faut avant tout déterminer le nombre de fois que cette boucle est répétée, ensuite le multiplier par la complexité du corps de cette boucle.
Il est parfois plus difficile de compter le nombre de répétitions
Mais d'accord qu'on analyse les boucles while comme les boucles for.
Code:

1 2 3 4 5 6 7 8 9 10 11 int PGCD(int A, int B){ int reste; reste = A % B; while (reste !== 0) { A = B; B = reste; reste = A % B; } return(B);
nombre de répétitions du while? pas évident sans calcul.
le for est plus "simple", c'est peut etre un abus de langage la facon dont j'utilise le mot simple.
Cependant j'espère m'être fait comprendre!

04/04/2007, 13h48
Jean-Marc.Bourguet

for(;cond;) est strictement equivalent a while(cond). Donc il doit y avoir les memes problemes en calcul de complexite. Ton prof parlait peut-etre d'une forme restreinte de for.

Quant au while() (et donc le for de C), il permet l'ecriture de boucles dont on ne sait meme pas si elles se terminent ou pas. Alors evaluer le nombre de passages...
04/04/2007, 13h49
Ulmo
Citation:

Envoyé par souviron34

Non, c'est parce que dans un swith il y a une seule évaluation (un seul test) et un branchement. Dans un if.else si il y a plusieurs valeurs (plusieurs else if) cela fait plusieurs évaluations.

J'ai pas regardé d'exemple avec un compilateur récent, mais dans celui que je connais (datant de 1998), les switchs sont compilés de 2 façons différentes :
- une suite de tests/goto (éventuellement des tests malins, du genre décrémenter la valeur et sauter si résultat nul, du genre DEC ECX / JEQ xxx / SUB ECX, 2 / JEQ yyy / ...)
- une table de pointeurs, et utilisation de la valeur testée comme index dans cette table
D'ailleurs en ASM, je ne voit pas comment on peut autrement. Donc si tes valeurs possibles (les différents case) ne sont pas assez regroupés, ton switch sera converti en une suite de if/else.
04/04/2007, 13h51
lun4t1k

Je ne parle pas de boucles infinies! celles ci mises a part, pour un algo qui termine, avec une complexité calculable!
Que de critères déterministes!
04/04/2007, 13h52
Médinoc

Il arrive même que gcc fasse les tests d'un switch() par dichotomie...
On peut faire pratiquement tout en fait.
Même réordonner certains cases s'ils se terminent tous par un saut (mais là, j'ai des doutes sur la véritable utilité de cette manoeuvre).
04/04/2007, 13h53
Jean-Marc.Bourguet

Citation:

Envoyé par lun4t1k

Je ne parle pas de boucles infinies! celles ci mises a part, pour un algo qui termine, avec une complexité calculables!
Que de critères déterministes!

Je n'ai pas parle des boucles infinies, mais de celles dont on ne sait pas si elles se terminent.
04/04/2007, 13h56
lun4t1k

Citation:

Envoyé par Jean-Marc.Bourguet

Je n'ai pas parle des boucles infinies, mais de celles dont on ne sait pas si elles se terminent.

Et alors?

while (reste !== 0) ou for(; reste !== 0 ; ) ne facilitent pas le calcul! alors qu'ils terminent. Mais c'est sûr que de calculer la complexité d'un algo sans preuve de terminaison... :aie:
C'est tout ce que je voulais mettre en avant !
04/04/2007, 14h00
Thierry Chappuis

Citation:

Envoyé par lun4t1k

Et alors?

while (reste !== 0) ou for(; reste !== 0 ; ) ne facilitent pas le calcul! alors qu'ils terminent. Mais c'est sûr que de calculer la complexité d'un algo sans preuve de terminaison... :aie:
C'est tout ce que je voulais mettre en avant !

La condition, c'est:

Code:

while (reste != 0)

Thierry

Citation:

Envoyé par Ulmo

J'ai pas regardé d'exemple avec un compilateur récent, mais dans celui que je connais (datant de 1998), les switchs sont compilés de 2 façons différentes :

une suite de tests/goto (éventuellement des tests malins, du genre décrémenter la valeur et sauter si résultat nul, du genre DEC ECX / JEQ xxx / SUB ECX, 2 / JEQ yyy / ...)
une table de pointeurs, et utilisation de la valeur testée comme index dans cette table

D'ailleurs en ASM, je ne voit pas comment on peut autrement. Donc si tes valeurs possibles (les différents case) ne sont pas assez regroupés, ton switch sera converti en une suite de if/else.

ça fait très très longtemps que je n'ai pas fait d'assembleur, et je n'ai pas regardé comment c'était décode par le compilo, mais le principe est très simple, il me semble :

à chaque case une valeur :
donc normalement un jmp

Il est certain que si c'et la deuxième manière qui est utilisée, c'est beaucoup plus rapide
Pour la première, si c'est une valeur simple (la valeur d'un entier), il n'y a pas de différence. Par contre, dans la plupart des cas où c'est utilisé, ce n'est pas un test simple sur une valeur entière prédéfinie (une constante), mais une comparaison au minimum avec une variable, souvent plusieurs tests ensemble.

Normalement ceci devrait être équivalent :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 if ( i == 3 ) { } else if ( i == 2 ) { } else if ( i == 1 ) { }
Et
Code:

1 2 3 4 5 6 7 8 9 10 switch ( i ) { case 1 : break ; case 2 : break ; case 3 : break ; }
Par contre , ceci ne devrait PAS être équivalent :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 if ( (j == var1) && (i == 3) ) { } else if ( (j == var2) && (i == 2) ) { } else if ( (j == var3) && (i == 1)) { }
et
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 switch ( i ) { case 3 : if ( j == var3 ) { } break ; case 2 : if ( j == var2 ) { } break ; case 1 : if ( j == var1 ) { } break ; }
A mons avis....

04/04/2007, 14h07
lun4t1k

??

Voir 40 message(s) de cette discussion en une page