Optimisation de code

**french_aspi** · 19/08/2008, 08h55

Bonjour
Puisque le calcul sur multi coeur semble ne pas marché avec ma version, je m'attaque au code.

Voici mon problème
J'ai deux colonne avec des numéros ( 2 colonnes de 200 000 lignes environ) et de doit former des triplets

Je m'explique

PAr exemple, j'ai
1 2
2 3
1 3

je reforme le triplet 1 2 3 et ainsi de suite pour tout le code

On comprends donc que els boucles for et while sont de la partie et MATLAB est bien méchant avec moi là

Il y en a pour 2 semaines de claul et c'est pas possible

Voici le morceau de code

Les 2 colonnes sont dans la variable VICS et je range mes triplets dans TA

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
 
 
AZ=1; 
                                                                                % Initialisation
for qa=1:xx                                                                           % Boucle externe
 
    if VICS(qa,1)~= VICS(qa,2)                                                        % condition de dséparation du doublet
       intermediaire=VICS(qa,2);                                                      % Affectation
            for qb=1:xx                                                               % Boucle externe 2                                                  
                if VICS(qb,2)== intermediaire                                         % Recherche d'un élément commun
                    intermed=VICS(qb,1);                                              % Affectation
                    for qc=1:xx                                                       % Boucle interne
                       if ((VICS(qc,1) == VICS(qb,1)) && (VICS(qc,2) == VICS(qa,1)))  % Recherche du 3 émé élement commun
                            za=VICS(qa,1);                                            % Attribution
                            zb=VICS(qa,2);                                            % Attribution
                            zc=VICS(qb,1);                                            % Attribution
                            if (zb ~= zc) && (za ~= zc)                               % Ecartement d'un cas de similitude
                                TA(AZ,1)=za;                                          % Attribution
                                TA(AZ,2)=zb;                                          % Attribution
                                TA(AZ,3)=zc;                                          % Attribution
                                AZ=AZ+1;
                             end
                        end  
                    end
                 end
            end
     end
end

**Jerome Briot** · 19/08/2008, 09h04

Envoyé par french_aspi

On comprends donc que els boucles for et while sont de la partie

Surtout pas

Code :

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

1
2
3
4
5
6
7
VICS = [1 2
        2 3
        1 3]
 
uVICS = unique(VICS(:));
 
TA = nchoosek(uVICS,3)

Bon maintenant, si tu lis bien la documentation de NCHOOSEK, tu verras qu'il y a une légère limitation à ce code

**LordPeterPan2** · 19/08/2008, 09h14

Envoyé par french_aspi

Bonjour
Puisque le calcul sur multi coeur semble ne pas marché avec ma version, je m'attaque au code.

Voici mon problème
J'ai deux colonne avec des numéros ( 2 colonnes de 200 000 lignes environ) et de doit former des triplets

Je m'explique

PAr exemple, j'ai
1 2
2 3
1 3

je reforme le triplet 1 2 3 et ainsi de suite pour tout le code

On comprends donc que els boucles for et while sont de la partie et MATLAB est bien méchant avec moi là

Il y en a pour 2 semaines de claul et c'est pas possible

Voici le morceau de code

Les 2 colonnes sont dans la variable VICS et je range mes triplets dans TA

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
 
 
AZ=1; 
                                                                                % Initialisation
for qa=1:xx                                                                           % Boucle externe
 
    if VICS(qa,1)~= VICS(qa,2)                                                        % condition de dséparation du doublet
       intermediaire=VICS(qa,2);                                                      % Affectation
            for qb=1:xx                                                               % Boucle externe 2                                                  
                if VICS(qb,2)== intermediaire                                         % Recherche d'un élément commun
                    intermed=VICS(qb,1);                                              % Affectation
                    for qc=1:xx                                                       % Boucle interne
                       if ((VICS(qc,1) == VICS(qb,1)) && (VICS(qc,2) == VICS(qa,1)))  % Recherche du 3 émé élement commun
                            za=VICS(qa,1);                                            % Attribution
                            zb=VICS(qa,2);                                            % Attribution
                            zc=VICS(qb,1);                                            % Attribution
                            if (zb ~= zc) && (za ~= zc)                               % Ecartement d'un cas de similitude
                                TA(AZ,1)=za;                                          % Attribution
                                TA(AZ,2)=zb;                                          % Attribution
                                TA(AZ,3)=zc;                                          % Attribution
                                AZ=AZ+1;
                             end
                        end  
                    end
                 end
            end
     end
end

Merci de m'aider car c'est urgent

Non elle ne sont pas de la partie. voici un exemple :

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
 
>> A=round(100*rand(9,2))
 
A =
 
    95    44
    23    62
    61    79
    49    92
    89    74
    76    18
    46    41
     2    94
    82    92
>> reshape(A(:),3,numel(A)/3)
 
ans =
 
    95    49    46    44    92    41
    23    89     2    62    74    94
    61    76    82    79    18    92
>> reshape(A(:),3,numel(A)/3)'
 
ans =
 
    95    23    61
    49    89    76
    46     2    82
    44    62    79
    92    74    18
    41    94    92

**french_aspi** · 19/08/2008, 10h04

Oui mais attends, j'ai penser à nchoosek
Le problème est que mon triplet, je ne connait pas les numéros à l'avance
je peux avoir 1 2 3 comme 8 9 32
De plus, dans mes colonnes, je peux avoir une suite de 1 à 100 sans les nombres 50 21 36 ..

Je ne vois donc vrt pas comment un nchoosek pourrait m'aider

Merci à vous

**french_aspi** · 19/08/2008, 10h10

De plus, lordpeterpan2, ton exemple à un problème :

Dans mon cas

1 2
2 3
1 3
5 6
7 8

Il faut 3 conditions pour former mon triplet :

que j'ai 1 2 ET 2 3 ET 1 3, il faut donc cette "permutation circulaire" pour former mon triplet, et là, y a un problème

**LordPeterPan2** · 19/08/2008, 11h19

Envoyé par french_aspi

De plus, lordpeterpan2, ton exemple à un problème :

Ahhhhhhhhh j'avais pas du tout compris le coup des permutations circulaire

**Jerome Briot** · 19/08/2008, 11h28

Deux triangles peuvent-ils partager la même arête ?

1 2
2 3
1 3
1 4
2 4

=> [1 2 3] et [1 2 4]

**Caro-Line** · 19/08/2008, 10h13

Juste en passant et sans vouloir déprimer qui que ce soit :
les boucles for ne sont pas vos ennemies.
Depuis les dernières versions de MATLAB (je ne sais plus laquelle)
elles sont suffisamment optimisées (en temps d'exécution)
et sont parfois plus rapides qu'un joli code "optimisé" en nombre de lignes de code.
Voir ce post : optimisation d'un code

Il ne faut pas donc perdre de vue que l'objectif est bien l'optimisation en temps.
Du coup il faudra peut-être tester effectivement à quoi ressemble ta matrice avant de choisir la méthode et avoir des méthodes différentes suivant la taille et le nombre d'éléments.

**Jerome Briot** · 19/08/2008, 10h15

Envoyé par french_aspi

1 2
2 3
1 3
5 6
7 8

Quel serait le résultat avec cette matrice ?

**french_aspi** · 19/08/2008, 11h13

le résultat serait le triplet 1 2 3

Autre exemple

1 5
1 8
5 8

Le triplet 1 5 8 ( il faut la permutation circulaire entre le 1 et le 5 et le 8)
Si tu veux, c'est comme si tu devait former un triangle et que 1 5 représente un des 3 cotés

Autre exemple

1 6
6 9
5 2

il te manque le couple 9 1 pour former ton triplet

Et ainsi de suite

Sauf que des triplets, j'en ai des 200 000 et pour 3 semaines de calcul avec mon code aujkourd'hui

Donc je suis vrt ennuyé là

**LordPeterPan2** · 20/08/2008, 08h39

Envoyé par caro95470

Juste en passant et sans vouloir déprimer qui que ce soit :
les boucles for ne sont pas vos ennemies.
Depuis les dernières versions de MATLAB (je ne sais plus laquelle)
elles sont suffisamment optimisées (en temps d'exécution)
et sont parfois plus rapides qu'un joli code "optimisé" en nombre de lignes de code.
Voir ce post : optimisation d'un code

Il ne faut pas donc perdre de vue que l'objectif est bien l'optimisation en temps.
Du coup il faudra peut-être tester effectivement à quoi ressemble ta matrice avant de choisir la méthode et avoir des méthodes différentes suivant la taille et le nombre d'éléments.

C'est sûr que si le programme en boucle for est plus rapide que le programme dit optimisé, alors faut pas hésiter.
Néanmoins, je reste persuader que tant qu'on peut se passer des boucles for, çà vaut le coup d'essayer.

**Jerome Briot** · 20/08/2008, 08h56

Envoyé par LordPeterPan2

Néanmoins, je reste persuader que tant qu'on peut se passer des boucles for, çà vaut le coup d'essayer.

La démarche rigoureuse sous MATLAB pour écrire un code optimisé :

utiliser des structures itératives (FOR, WHILE) non optimisées (+commentaires)
optimiser les boucles (préallocation...) (+commentaires)
vectoriser (+ commentaires)

Et surtout, conserver une version des trois fichiers afin de pouvoir :

comparer les différentes versions entre elles (il y a parfois de bonnes surprises)
conserver au moins un code (devinez lequel) qui se rapproche le plus de la structure algorithmique => + lisible par ceux/celles qui devront relire/ mettre à jour le code
pouvoir utiliser l'une ou l'autre des versions suivant les cas

Optimisation de code

MATLAB

Vue hybride

Discussions similaires

Partager

Partager