Probleme optimisation de boucles

**panda31** · 05/04/2006, 16h21

Bonjour a tous tout d'abord,

je suis en stage la et je dois optimiser un programme (noyau de calcul de modification des orientations atomiques des constituants d'une molecule apres une deformation).
Je ne suis qu'en L2 et mes connaissances en C sont suffisantes... MAIS... J'ai un pb avec du code... Je travaille sur une machine Sun SunBlade 1500 sous Solaris (JE VEUX MON BEAU UBUNTU)...

Voila l'extrait de code original :

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
22
23
24
 
    /*APPEL DE LinMode => Indicateurs de temps CallLinMode1 et CallLinMode2 */
    CallLinMode1 = time(NULL); /*MODIFIE LE 05/04/06*/
    printf("CallLinMode1 = %lf\n",CallLinMode1);
 
    k = 0;
 
 
    for (j = 0; j < Natomes; j++){ 
		for (i = 0; i <= 2 ;i++) {
			if (CMOD[j][i] == 1) {/*par defaut on traite tous les modes, plus tard on pourra choisir */
  		  		LinMode(Natomes, j, i, k, nj, nk, En, err, dx, nl, gg, D, M);
				kk[j][i] = k;												
	       	 	k = k+1;
		}    	    	    	
	} 			
    }
    CallLinMode2 = time(NULL); /*MODIFIE LE 05/04/06*/
    printf("CallLinMode2 = %lf\n",CallLinMode2); 
    TEMPS_BOUCLE_LINMODE    = difftime(CallLinMode2,CallLinMode1) ; /*MODIFIE LE 05/04/06*/
    printf("******************************************\n\n");
    printf("temps en s = %lf\n", TEMPS_BOUCLE_LINMODE);    
    printf("temps en min = %lf\n", TEMPS_BOUCLE_LINMODE/60) ;
    printf("\n\n******************************************\n\n");

On voit bien ici un bel exemple de boucle longue... A lui suel, cet extrait dure 30 minutes environ pour s'executer (Natomes est une variable qui fait dans nos tests 46)...

Je me suis demande si la longueur venait de la boucle du main ou de la fonction elle-meme :

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
void LinMode(int Natomes, int N, int in, int k, int nj, int nk, double En, double err, double
*dx,int *nl, int *gg, double **D, double **M)
{
    time_t LM_BEGIN=time(NULL), LM_END ;
    double eps, *ddx , LM_Duree ;
    int i, j, n, nn, ii, it;    
    ddx=vec(3 * Natomes);    
    puts("LinMode\n");
    eps = 10. * err;
    it = 3 * Natomes - 6;     
    for (i = 0; i < 3 * Natomes; i++) {
	dx[i] = 0.;	
    }
    ii = 3 * nl[N] + in;
    if (ii == it) {
        ii = it - 1;
    }    
    printf("ii=%d\n",ii);    
    dx[ii] = 1.;    
    while (eps > err) {
	for (i = 0; i < it ; i++) {
	    ddx[i] = dx[i];
	    if (i != ii) {
		for (j = 0; j < it ; j++) {
		    if (i != j) {
		       dx[i] += D[i][j] * dx[j];		       		    
		    }
		}	    
	    dx[i] = -dx[i] / D[i][i];
	    }	    	    
	    ddx[i] -= dx[i];	    	    	
	}
	eps = Norme(ddx,it); /* normalisation de ddx pas nécessaire !*/	
    }     
    En = Energie(Natomes, dx, D);      
    printf("Energie = %f\n",En);      
    for (n = 0; n < Natomes - 3; n++) { 
        nn = 3 * n;
	ii = gg[n] * 3;        
        M[ii][k] = dx[nn];
	M[ii + 1][k] = dx[nn + 1];
	M[ii + 2][k] = dx[nn + 2];
    }  
    nn = 3 * Natomes - 9;
    M[3 * nk][k] = dx[nn]; 
    M[3 * nk + 1][k] = dx[nn + 1];
    M[3 * nj][k] = dx[nn + 2];     
    M[3 * Natomes][k] = En;
    M[3 * Natomes + 1][k] = 3 * N + in;    	      
 
    LM_END=time(NULL) ;
    LM_Duree=difftime(LM_END,LM_BEGIN) ;
    printf(" Duree (en secondes) d'execution pour cet appel = %lf\n", LM_Duree) ;
}

A mon avis c'est le passage du main qui est en faute... mais comment optimiser ce bout de code... ?
De toute facon, la suite de mon stage consistera a passer sur super calculateur et/ou machine parallele mais bon autant d'abord optimiser l'algo !

Si vous avez une idee, contactez-moi svp...

**Menthe_a_l_eau** · 05/04/2006, 21h31

Salut

Selon les boucle les temps d'execution sont variables.

un court switch case sera plus long que des if elseif.

boucle for plus longue que while

**hegros** · 05/04/2006, 21h44

C'est plus un probléme algorithmique qu'un probléme lié au langage C en java ou en C# tu aurais le même probléme je suppose. Il te faut trouver l'algo d'une complexité moindre que ce que tu as la...Pas toujours évident clair.

**Franck.H** · 05/04/2006, 22h41

J'crois que je vais écrire un article sur comment écrire un "beau" code

**PRomu@ld** · 05/04/2006, 23h17

Oui, c'est vrai...

Des noms de variables explicites, une indentation parfois bizarre ...

Mais pour en revenir à ta question, est ce qu'une étude algorithmique à eu lieu parce que l'optimisation en C n'apportera pas grand chose sur ton programme si l'algorithme utilisé n'est pas le bon.

Juste comme ça, une double boucle for appelée dans une boucle while, le tout appelé dans une double boucle for ...

**panda31** · 06/04/2006, 08h35

Je vous l'accorde le code est degueulasse... Je suis arrivé dans mon labo de stage et tout ca etait deja fait. Perso, n'importe quel codeur connaissant les moindres regles de Genie logiciel aurait compris qu'il faaut penser des le debut au deboguage et a la maintenance... Là, ben on voit rien...

Mon stage dure (que) 4 mois et je ne sais pas si j'aurais le temps d'etablir un algo depuis le code... On avance a reculons là !

Cote "optimisation" de l'algo... Moi je suis prêt mais yen a pas pour le moment... Vous savez les chercheurs...

**PRomu@ld** · 06/04/2006, 09h06

Vous savez les chercheurs...

T'a quelque chose contre les chercheurs ?

Mon stage dure (que) 4 mois et je ne sais pas si j'aurais le temps d'etablir un algo depuis le code...

Il n'y a pas de doc avec le code ? T'a pas la personne qui a fait le code sous la main ?

**panda31** · 06/04/2006, 09h15

Je n'ai strictement rien contre les chercheurs mais MES chercheurs (enfin, j'ai pas gardé la facture...

), sont assez bordéliques... des physiciens, la théorie du chaos en prime !!!

Aucune documentation, aucun cahier de recettes, aucun commentaire algorithmique...

Bref, c'est la caca...

**Matthieu Brucher** · 06/04/2006, 09h27

Ouais, t'as qqch contre les chercheurs

?
Bon, commence par découper ta fonction en sous-blocs de 5-10 lignes maximum. Regarde ce qu'elle fait et nomme-la de manière explicite, ainsi que les variables.

**panda31** · 06/04/2006, 09h31

Envoyé par PRomu@ld

Oui, c'est vrai...
Juste comme ça, une double boucle for appelée dans une boucle while, le tout appelé dans une double boucle for ...

Pour l'indenation, c'est juste un pb de copier-coller.

La boucle While avec les deux for imbriqués ne me plait pas non plus.

J'aimerais en effet refondre entierement l'algo de cette fonction LinMode mis je ne sais pas trop par quoi commencer (niveau L2 IUP Info)...
Est-il préférable de séparer les POUR du PENDANT QUE et de faire un WHILE portant les resultats calculés dans les FOR placés en amont ? Serait-ce utile de transformer tout ou partie des boucles en récurisivité ? Pour choisir entre toutes les solutions qui s'offrent, il me faudrait des connaissances complémentaires au calcul (ou la détermination) de la complexité.

**panda31** · 06/04/2006, 09h33

Envoyé par Miles

Ouais, t'as qqch contre les chercheurs

?
Bon, commence par découper ta fonction en sous-blocs de 5-10 lignes maximum. Regarde ce qu'elle fait et nomme-la de manière explicite, ainsi que les variables.

Ok, je procède et je vous recontacte si jamais. En tout cas, merci beaucoup de votre aide. Ce forum est super et le site avec. (COURS Recursivité et Megabook du C m'ont bcp aidés).

**panda31** · 06/04/2006, 10h51

Bon, j'ai commencé...
Voilà à peu près ce que j'ai fait. Pour le moment, j'ai remlacé le while(eps>err) par un appel récursif de paramètre eps.
Ensuite, il y avait une initialisation d'un vecteur à 0. par une boucle FOR que j'ai remplacé par une MACRO.

Maintenant, je voudrais m'attaquer aux FOR mais leur structure est biscornue et leur actions interdépendantes. Pour le moment, je bloque !

Mais cela va s'eclaircir... Ils l'ont même dit à la météo !

OK OK je sors