Discussion :

[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

[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?

[souviron34]

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..

[souviron34]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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)

[Thierry Chappuis]

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! )

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

Thierry

[vinzzzz]

Si j'ai bien compris, quand je fais:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[vinzzzz]

Ok donc y'a encore vraiment moyen d'améliorer tout ca... Merci pour toutes ces précisions.

[souviron34]

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

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

[vinzzzz]

L'ignorant qui s'ignore

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.

[souviron34]

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"..

[lun4t1k]

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.

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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!

[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...

[Ulmo]

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.

[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!

[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).

[Jean-Marc.Bourguet]

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.

[lun4t1k]

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...
C'est tout ce que je voulais mettre en avant !

[Thierry Chappuis]

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...
C'est tout ce que je voulais mettre en avant !

La condition, c'est:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

while (reste != 0)

Thierry

[souviron34]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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....

[lun4t1k]

??