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

**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** · 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]

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

Pour ton exemple, construit la matrice A de graphe :
Si V =
1 2
2 3
1 3
5 6
7 8

Alors A =

A =

1 1 1 0 0 0 0 0
1 1 1 0 0 0 0 0
1 1 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
0 0 0 0 0 0 1 1
0 0 0 0 0 0 1 1

Dans ces cas là tes triplet peuvent être obtenu comme suit :

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
 
T=[];
% qu'une seule boucle sur les lignes
for ind_l = 1:size(A,1)
    % je cherche les doublons contenant ind_l
    ind = find(A(ind_l,:)) ;
    if ~isempty(ind)
        % je récupere les doublons des doublons avec ind_l (donc les triplet contenant ind_l
        [ind_i,ind_j]=find(A(ind,ind));
        ind_i = ind(ind_i);
        ind_j = ind(ind_j);
        if ~isempty(ind_i)
            % juste pour éviter de copier 3 fois un meme triplet
            ind = find( (ind_i<ind_j) & (ind_j<ind_l) );
            if ~isempty(ind)
                ind_i = ind_i(ind);
                ind_j = ind_j(ind);
                ind_k = repmat(ind_l,1,numel(ind)) ;
                T = [T [ind_i ;ind_j ;ind_k]];
            end;
        end;
    end;
end;

edit : j'ai rajouté des commentaires

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

Pour construire A (attention je prends la cas ou A est creuse) :

Code :

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

1
2
3
4
5
6
7
 
n=max(max(V));
A=sparse(n,n);
A(V(:,1)+n*(V(:,2)-1))=1;
A=A+A'+speye(n);
// pour voir la tete de A : 
spy(A);

**french_aspi** · 19/08/2008, 12h30

oui Dut, t'as compris, ils peuvent partagés

Il faudra juste faire attention que le triplet 123 est égal au triplet 132 = 231 = 321 = 213,... c'est commutatif sur le triplet

Pour peterpan2, je ne comprends pas du tout ce qu'est ta matrice graphe A

**LordPeterPan2** · 19/08/2008, 13h07

Envoyé par french_aspi

oui DUT, t'as compris, ils peuvent partagés

Il faudra juste faire attention que le triplet 123 est égal au triplet 132 = 231 = 321 = 213,... c'est commutatif sur le triplet

Pour peterpan2, je ne comprends pas du tout ce qu'est ta matrice graphe A

A(i,j) = 1 si i et j sont connectés entre eux :

Je reprends ton exemple :

V =
1 2
2 3
1 3
5 6
7 8

alors A(1,2) = 1, A(2,3)=1, ...
Pour avoir une matrice symétrique (plus pratique pour les calculs), on écrit

Code :

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

A=A+A'+speye(n)

pour avoir A(i,j) = A(j,i) et A(i,i) = 1 pour tout i,j

**french_aspi** · 19/08/2008, 13h12

moui, je comprends en gros
seulement, quand j'execute le code, j'ai un problème ici :

Code :

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

A(V(:,1)+8*(V(:,2)-1))=1;

Il me met qu'il ne peut pas assigné

De plus LordPeterPan2, comment as tu eu l'idée de faire comme ça, car je dois avouer que ta méthode est assez élégante comparée à la mienne.

**french_aspi** · 19/08/2008, 13h14

PS: pourquoi cette ligne, je comprends pas:

Code :

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

A(V(:,1)+8*(V(:,2)-1))=1;

D'ou sort le 8 et compagnie ?

**LordPeterPan2** · 19/08/2008, 13h20

Envoyé par french_aspi

moui, je comprends en gros
seulement, quand j'execute le code, j'ai un problème ici :

Code :

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

A(V(:,1)+n*(V(:,2)-1))=1; % scousez je me suis tromper j'avais mis 8 car dans ton exemple V était de taille 8x2 mais dans le cas général nx2

Il me met qu'il ne peut pas assigné

De plus LordPeterPan2, comment as tu eu l'idée de faire comme ça, car je dois avouer que ta méthode est assez élégante comparée à la mienne.

Je suis habitué à travaillé matriciellement plutôt qu'avec des boucle for, de plus la matrice A est une matrice de graphe (connu dans le milieu des graphes).

La matrice A sert à voir facilement ce que l'on appelle les cliques (une cliques est un n-uplet dont les points sont connectés deux à deux)

**LordPeterPan2** · 19/08/2008, 13h21

Envoyé par french_aspi

PS: pourquoi cette ligne, je comprends pas:

Code :

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

A(V(:,1)+8*(V(:,2)-1))=1;

D'ou sort le 8 et compagnie ?

héhé justement le 8 est une erreur V était de taille 8x2. Dans le cas général V de taille n x 2,

Code :

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

A(V(:,1)+n*(V(:,2)-1))=1;

**LordPeterPan2** · 19/08/2008, 13h25

Envoyé par french_aspi

moui, je comprends en gros
seulement, quand j'execute le code, j'ai un problème ici :

Code :

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

A(V(:,1)+8*(V(:,2)-1))=1;

Il me met qu'il ne peut pas assigné

De plus LordPeterPan2, comment as tu eu l'idée de faire comme ça, car je dois avouer que ta méthode est assez élégante comparée à la mienne.

Bon mis à part de remplacer le 8 par n

Il te met toujours qu'il ne peut pas assigner ???

A est bien de taille n x n avec n le maximum des deux colonnes de V ?

**french_aspi** · 19/08/2008, 18h00

Excellent PeterPAn2, c''est vraiment génial, je te remercie
tu mérites que je t'envoie une bonne bouteille de vin de ma cave après l'épine que tu viens de me retirer du pied

Optimisation de code

MATLAB

Discussions similaires

Partager

Partager