Défi n°2 : Pourquoi les matrices et les vecteurs ne s'entendent pas mieux ?
Venez relever les défis MATLAB.

Le , par Jerome Briot, Rédacteur/Modérateur
C'est bien dommage

Prenons le cas d'une matrice A et d'un vecteur B :

Code : Sélectionner tout
1
2
3
A = [1 2 ; 3 4 ; 5 6 ; 7 8]

B = [2 4]
Code : Sélectionner tout
1
2
3
4
5
6
7
8
9
10
11
A =

     1     2
     3     4
     5     6
     7     8


B =

     2     4
Il est relativement fréquent que l'on soit amené à effectuer une opération entre la première colonne de A ([1 3 5 7]) et la première valeur de B (2) et la seconde colonne de A ([2 4 6 8]) et la seconde valeur de B (4).

Par exemple, une simple soustraction, A - B qui renverrait :

Code : Sélectionner tout
1
2
3
4
5
6
ans =

    -1    -2
     1     0
     3     2
     5     4
Malheureusement si l'on fait directement la soustraction entre la matrice et le vecteur, MATLAB ne veut rien savoir :

Code : Sélectionner tout
1
2
3
>> A-B
??? Error using ==> minus
Matrix dimensions must agree.
Il faut donc utiliser une autre méthode : boucle FOR-END, code vectorisé, fonction spéciale...

------------------------------------------------------

Défi : Trouver la méthode la plus rapide pour effectuer une soustraction entre les colonnes d'une matrice et un vecteur


Contrainte
: le code devra être contenu dans un fichier m fonction dont le nom sera votre pseudo (si votre pseudo n'est pas accepté comme nom de fonction, prenez un nom similaire ). Cette fonction prendra en argument d'entrée une matrice A et un vecteur B et retournera en argument de sortie une matrice C résultat.

Par exemple, si je (Dut) propose une solution, la première ligne du fichier sera :

Code : Sélectionner tout
function C = Dut(A,B)
Notes :

  • les noms de variable A,B,C sont donnés à titre indicatif et peuvent être modifiés
  • rien n'empêche de faire appel à d'autres fichiers à l'intérieur de matvec.m


Alors, quelle serait la méthode la plus rapide sous MATLAB selon vous ?

A vous de jouer... donnez vos solutions à la suite de ce message


------------------------------------------------------


Les solutions proposées :

mr_samurai :
Code : Sélectionner tout
1
2
3
function C = mr_samurai(A, B)

C = A - ones(size(A,1),1)*B;
vinc-mai :
Code : Sélectionner tout
1
2
3
function C = vinc_mai(A,B)

C = A - repmat(B,size(A,1),1);
Caro-line :
Code : Sélectionner tout
1
2
3
4
5
6
7
function C = caroline(A, B)

[m,n] = size(A);
C = zeros(size(A));
for i=1:m
    C(i,:) = A(i,:)-B;
end
tug83
Code : Sélectionner tout
1
2
3
function C = tug83(A,B)

C = bsxfun(@minus, A, B);
Dut (voir le fichier MEX ici) :
Code : Sélectionner tout
1
2
3
function C = Dut(A,B);

C = Dutmex(A,B);
------------------------------------------------------


Code utilisé pour la comparaison :

Code : Sélectionner tout
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
function [T,users,N] = microDefi2(num)

if nargin == 0
    num = 7;
end

% Taille croissante des données
N = 10.^(0:num-1);

% Données initiales
iA = [1 2 ; 3 4 ; 5 6 ; 7 8];
iB = [2 4];

% Membres participant au défi
users = {'mr_samurai' 'vinc-mai' 'caroline' 'tug83'};
nusers = numel(users);

mt = 5;
nT = 1;

for n=1:numel(N)
    
    % Augmentation de la taille des données au fur et à mesure
    A = repmat(iA,1,N(n));
    B = repmat(iB,1,N(n));
    
    %% Solution de mr_samurai
    for k=1:mt
        tic
            C = mr_samurai(A,B);
        t(k) = toc;
        clear C
    end
    T(nT,1) = mean(t);
    
    %% Solution de vinc-mai
	for k=1:mt
        tic
            C = vinc_mai(A,B);
        t(k) = toc;
        clear C
    end
    T(nT,2) = mean(t);

    %% Solution de Caro-line
    for k=1:mt
        tic
            C = caroline(A,B);
        t(k) = toc;
        clear C
    end
	T(nT,3) = mean(t);
      
    %% Solution de tug83
    if exist('bsxfun','builtin')==5 % Cette fonction n'est pas disponible avec toutes les versions
        
        for k=1:mt
            tic
                C = tug83(A,B);
            t(k) = toc;
            clear C
        end  
        T(nT,4) = mean(t);
    else
        T(nT,4) = nan;
    end
    
    %% Fin des solutions proposées
    nT = nT +1;
    
end
------------------------------------------------------


Temps d'exécution :

MATLAB R2008a - Windows XP - 2GHz - 2Go Ram
Code : Sélectionner tout
1
2
3
4
5
6
7
8
    N       mr_samurai	vinc-mai	caroline	tug83		Dut
      1     0.000848	0.000932	0.001002	0.000739	0.000249	
     10     0.000036	0.000076	0.000020	0.000045	0.000012	
    100     0.000036	0.000081	0.000018	0.000055	0.000019	
   1000     0.000107	0.000126	0.000053	0.000164	0.000106	
  10000     0.001491	0.001802	0.000913	0.001691	0.001289	
 100000     0.021650	0.033351	0.033862	0.018619	0.017151	
1000000     0.242351	0.342116	0.294612	0.189642	0.179889
MATLAB R2007a - Windows Vista SP1 - 2GHz - 2Go Ram
Code : Sélectionner tout
1
2
3
4
5
6
7
8
    N       mr_samurai	vinc-mai	caroline	tug83	
      1     0.166230	0.000183	0.003227	0.002319	
     10     0.001539	0.000057	0.000020	0.000032	
    100     0.000035	0.000065	0.000019	0.000045	
   1000     0.000185	0.000277	0.000150	0.000202	
  10000     0.003575	0.003802	0.003620	0.002428	
 100000     0.027099	0.030994	0.028084	0.020660	
1000000     0.264510	0.301678	0.280330	0.207564
MATLAB R2008b - Linux 64bits - Processeur 8 cœurs
Code : Sélectionner tout
1
2
3
4
5
6
7
8
    N       mr_samurai	vinc-mai	caroline	tug83		Dut
      1     0.000021	0.000043	0.000014	0.000025	0.000009	
     10     0.000013	0.000039	0.000009	0.000022	0.000008	
    100     0.000017	0.000042	0.000011	0.000029	0.000014	
   1000     0.000080	0.000079	0.000042	0.000098	0.000074	
  10000     0.001122	0.000519	0.000773	0.001603	0.000893	
 100000     0.017785	0.023169	0.025011	0.011389	0.012374	
1000000     0.185730	0.246647	0.260227	0.115151	0.127354
Matlab 2008a - Linux 32 bits - 3.2GHz - 2Go

Code : Sélectionner tout
1
2
3
4
5
6
7
8
    N       mr_samurai	vinc-mai	caroline	tug83		Dut
      1     0.000078	0.000135	0.000062	0.000084	0.000327	
     10     0.000036	0.000131	0.000026	0.000062	0.000052	
    100     0.000050	0.000142	0.000039	0.000082	0.000073	
   1000     0.000222	0.000157	0.000055	0.000193	0.000163	
  10000     0.002153	0.001704	0.000903	0.001920	0.001592	
 100000     0.023430	0.027308	0.028055	0.019134	0.018004	
1000000     0.247297	0.259067	0.275122	0.186231	0.174071
  • N est l'ordre de grandeur du nombre de colonne de A (A possède 4*N colonnes)
  • les résultats sont donnés en secondes

------------------------------------------------------


Vous avez aimé cette actualité ? Alors partagez-la avec vos amis en cliquant sur les boutons ci-dessous :


 Poster une réponse

Avatar de Jerome Briot Jerome Briot - Rédacteur/Modérateur https://www.developpez.com
le 22/10/2008 à 22:10
Le premier message a été mis à jour avec les temps d'exécution pour des matrices de différentes tailles.

Si certains pouvaient faire tourner la fonction microDefi2.m et me retourner la variable T dans un fichier mat avec la configuration de l'ordinateur (OS, processeur), on pourrait faire un semblant de comparatif par machine

A utiliser comme ceci :

Code : Sélectionner tout
T = microDefi2;
Si une erreur mémoire survient, essayez comme ceci :

Code : Sélectionner tout
1
2
num = 6;
T = microDefi2(num);
En faisant décroitre num (entier) jusqu'à ce que ça marche.

Pensez à nettoyer MATLAB avant d'exécuter le code :
Code : Sélectionner tout
clear all
Pour ceux qui utilisent une version récente, pensez à mentionner si vous utilisez le multithreading
Avatar de Jerome Briot Jerome Briot - Rédacteur/Modérateur https://www.developpez.com
le 22/10/2008 à 22:11
Citation Envoyé par paradize3 Voir le message
il existe des version mex plus rapides en general
Voila une idée que personne ne semble avoir creusé... sans parler d'utiliser un MEX de repmat, je rappelle que les structures itératives peuvent aussi être intégrées dans un fichier MEX...

Quelqu'un veut essayer ?
Avatar de Caro-Line Caro-Line - Expert éminent sénior https://www.developpez.com
le 22/10/2008 à 22:25
Voilà.

MATLAB R2007a - Windows Vista SP1 - 2GHz - 2Go Ram

[Edit=Dut]
Avatar de paradize3 paradize3 - Membre averti https://www.developpez.com
le 23/10/2008 à 4:55
Citation Envoyé par paradize3 Voir le message
Code : Sélectionner tout
1
2
3
4
5
6
7
8
9
10
%---- S4
C = zeros(size(A));
tic
for z=1:nb
    for u=1:size(A,2)    
        C(:, u) = A(:, u) - B(u);
    end
end
toc
[Edit = Dut] Cette solution est déjà donnée par mr_samurai
pas tout a fait!! compare precisemment, et teste
je pense que ma version devrait etre plus rapide (dans le cas ou le nombre de lignes est plus grand que le nombre de colonnes), de plus elle est plus efficace au niveau du cache CPU..

Salutations,

Greg
Avatar de paradize3 paradize3 - Membre averti https://www.developpez.com
le 23/10/2008 à 5:38
Citation Envoyé par paradize3 Voir le message

plus rapide dans le cas ou le nombre de lignes est plus grand que le nombre de colonnes
ce qui est l'oppose de ton test mais c'est pas grave lol
Avatar de tug83 tug83 - Expert confirmé https://www.developpez.com
le 24/10/2008 à 13:30
Sous Linux 64-bit , 8 cores , sous R2008b
J'ai zippé le MAT-file
Avatar de Jerome Briot Jerome Briot - Rédacteur/Modérateur https://www.developpez.com
le 24/10/2008 à 13:44
C'est vrai que pour les processeurs multicoeurs, il peut être intéressant de faire l'essai avec le multithread aussi...
Avatar de Jerome Briot Jerome Briot - Rédacteur/Modérateur https://www.developpez.com
le 27/10/2008 à 21:01
Citation Envoyé par Dut  Voir le message
je rappelle que les structures itératives peuvent aussi être intégrées dans un fichier MEX...

Quelqu'un veut essayer ?

Bon ben je me lance...

Le fichier Dutmex.c :
Code C : Sélectionner tout
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
#include "mex.h" 
  
void mexFunction( int nlhs, mxArray *plhs[], 
                  int nrhs, const mxArray *prhs[]) 
{ 
int i, j, m ,n; 
double *M, *X, *P; 
  
m = mxGetM(prhs[0]); 
n = mxGetN(prhs[0]); 
  
M = mxGetPr(prhs[0]); 
X = mxGetPr(prhs[1]); 
  
plhs[0] = mxCreateDoubleMatrix(m, n, mxREAL); 
  
P = mxGetPr(plhs[0]); 
  
j=0; 
for (i = 0; i < m*n; i++)  
    { 
    j = (i / m);      
    P[i]=M[i]-X[j]; 
    } 
}

A compiler comme ceci :

Code : Sélectionner tout
mex Dutmex.c
Et le fichier m qui va avec :

Code : Sélectionner tout
1
2
3
function C = Dut(A,B); 
 
C = Dutmex(A,B);
Avatar de Jerome Briot Jerome Briot - Rédacteur/Modérateur https://www.developpez.com
le 27/10/2008 à 21:12
Merci de faire tourner les nouveaux code pour pouvoir mettre les résultats à jour...

Avatar de vinc-mai vinc-mai - Membre éprouvé https://www.developpez.com
le 28/10/2008 à 15:29
Voici mes résultats:
Code : Sélectionner tout
1
2
3
4
5
6
7
   0.000078200000000   0.000134600000000   0.000062400000000   0.000084200000000   0.000327200000000
   0.000036400000000   0.000131000000000   0.000026000000000   0.000062200000000   0.000052400000000
   0.000050000000000   0.000142400000000   0.000039000000000   0.000082400000000   0.000072600000000
   0.000222000000000   0.000157200000000   0.000055000000000   0.000192800000000   0.000162600000000
   0.002152600000000   0.001704200000000   0.000903200000000   0.001920200000000   0.001592400000000
   0.023429800000000   0.027307800000000   0.028054800000000   0.019134200000000   0.018003600000000
   0.247296600000000   0.259066800000000   0.275122400000000   0.186231000000000   0.174070600000000
Matlab 2008a Linux 32 bits 3.2GHz. Ram: 2Go

[Edit=Dut] Premier post mis à jour
Avatar de tug83 tug83 - Expert confirmé https://www.developpez.com
le 30/10/2008 à 15:39
Donc après avoir modifié microdefi2.m pour rajouter l'utilisateur Dut et apres avoir mexé ...j'arrive premier sur la même Linux 64-bits 8 cores (multithreading on) en 8b

[Edit=Dut] Oui mais tout le monde n'a pas un 8 cœurs
Résultats mis à jour dans le premier post
Contacter le responsable de la rubrique MATLAB