fonction min pour un vecteur (optimisation)

Version imprimable

Bonjour,

J'ai besoin de faire une recherche d'un minimum dans un ensemble de valeurs.

J'ai deux vecteurs de même dimension 'n' :
- un vecteur 'A' contenant des '0' ou des '1'.
- un vecteur 'B' contenant des nombres quelconques.
Par ailleurs, je connais le nombre 'k' de valeurs '1' du vecteur 'A'.

Je souhaite trouver la valeur minimum du vecteur 'B' restreint aux indices dont le vecteur 'A' vaut '1'...

J'ai réalisé deux solutions :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 ind = 1; while( ( A( i ) ~= 1 ) & ( ind < n ) ) ind = ind + 1; end mini = B( ind ); ind = ind + 1; for( i = ind : n ) if( A( i ) == 1 ) if( B( i ) < mini ) mini = B( i ); end end end
Je recherche le premier indice du tableau 'A' qui vaut '1'. Puis j'initialise la valeur minimum 'mini' avec la valeur du tableau 'B' à cet indice. Ensuite, je parcours le tableau 'A' et à chaque fois que j'ai un '1', je vérifie si la valeur du tableau 'B' est inférieure à la valeur minimum 'mini'.
Code:

1 2 3 4 5 6 7 8 9 10 aTempVect = zeros( 1 , k ); j = 1; for( i = 1 : n ) if( A( i ) == 1 ) aTempVect( j ) = B( i ); j = j + 1; end end mini = min( aTempVect );
Je crée un vecteur temporaire 'aTempVect' de dimension le nombre 'k' de '1' du tableau 'A', puis je le remplis avec les valeurs du tableau 'B' dont les valeurs des indices valent '1' dans le tableau 'A'. Enfin j'utilise la fonction MATLAB 'min' au vecteur 'aTempVect'. La création de ce vecteur temporaire 'aTempVect' ne sert qu'à obtenir la valeur minimum grâce à la fonction 'min' MATLAB.

Comme les valeurs de 'n' et 'k' sont très importantes et que je ne connais pas l'algorithme MATLAB de la fonction 'min', je souhaite savoir laquelle des deux solutions se révèlera la plus rapide.

Merci beaucoup de vos réponses.

22/09/2010, 10h41
Youni92

Essais ça:

Code:

Minimum = min(B(A==1))
22/09/2010, 10h50
MicBeastKiller

Merci de ta réponse,

Néanmoins, je souhaite avoir plus d'informations sur l'algorithme utilisé par MATLAB pour la fonction 'min' ainsi que la notion de vecteur.

Si en créant un vecteur et en le remplissant, ce vecteur contient aussi des attributs tels que sa taille, son min, son max, ... ; la deuxième solution ou ta troisième sera peut-être plus efficace en temps (mais peut-être pas en espace).
Sinon, la première solution est plus adaptée
22/09/2010, 12h27
Youni92

La fonction 'min' peut te donner le minimum d'un vecteur et son emplacement:

Code:

[C, I] = min(A);

Code:

help min

La solution que je t'ai donné est de loin la plus rapide des 3, puisqu'elle exploite les qualités de Matlab, à savoir le travail vectoriel, et n'utilise pas de longue boucle.

En gros:
B(A==1) => Matlab travail seulement sur les valeur de B ayant les mêmes indices que les valeur égale à 1 dans A.
min(B(A==1)) => Te donne le minimum des valeurs sélectionnées dans B

Si ce n'est pas ce que tu souhaite, soit plus précis, ou montre un exemple de ce que tu veux avoir.

Il "suffit" de comparer les différents codes :

Code:

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
function test
 
kt = 1;
kn = 6;
 
for n = 10.^(3:kn)
 
    A = rand(n,1)>.3;
    k = sum(A);
 
    B = rand(n,1);
 
    t = zeros(1,20);
 
    for i=1:20
        tic
        mini = MicBeastKiller_1(A,B);
        t(i) = toc;
    end
 
    T(kt,1) = mean(t);
 
    for i=1:20
        tic
        mini = MicBeastKiller_2(A,B,k);
        t(i) = toc;
    end
 
    T(kt,2) = mean(t);
 
    for i=1:20
        tic
        mini = Youni92(A,B);
        t(i) = toc;
    end
 
    T(kt,3) = mean(t);
 
    kt = kt+1;
end
 
figure
h = plot(T);
legend(h,{'MicBeastKiller_1' 'MicBeastKiller_2' 'Youni92'},'location','NorthWest')
set(gca,'xtick',1:kt-1,'xticklabel',num2str(10.^(3:kn).'))
xlabel('Taille du vecteur')
ylabel('Temps (s)')

avec

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function mini = MicBeastKiller_1(A,B)
 
n = numel(A);
 
ind = 1;
while( ( A( ind ) ~= 1 ) && ( ind < n ) )
    ind = ind + 1;
end
mini = B( ind );
ind = ind + 1;
for( i = ind : n )
    if( A( i ) == 1 )
        if( B( i ) < mini )
            mini = B( i );
        end
    end
end

Code:

1
2
3
4
5
6
7
8
9
10
11
12
function mini = MicBeastKiller_2(A,B,k)
n = numel(A);
 
aTempVect = zeros( 1 , k );
j = 1;
for( i = 1 : n )
    if( A( i ) == 1 )
        aTempVect( j ) = B( i );
        j = j + 1;
    end
end
mini = min( aTempVect );

Code:

1
2
3
function mini = Youni92(A,B)
 
mini = min(B(A==1));

J'ai fait le calcu de k en dehors de MicBeastKiller_2 car la phrase suivante laisse entendre que le nombre de 1 dans A est connu d'avance.

Citation:

Envoyé par MicBeastKiller

Par ailleurs, je connais le nombre 'k' de valeurs '1' du vecteur 'A'.

Sinon, il faudra intégrer sum(A) dans MicBeastKiller_2.

:idea: Si d'autres personnes veulent s'essayer à ce petit jeu... ils sont bien entendu les bienvenus pour proposer leur solution d'optimisation ;)

Maintenant, je n'ai trouvé aucune information concernant l'algorithme utilisé par la fonction MIN de MATLAB :?

23/09/2010, 10h31
MicBeastKiller

Merci beaucoup de vos réponses.

@Youni92 :

Citation:

La fonction 'min' peut te donner le minimum d'un vecteur et son emplacement

Je le sais bien, mais cela ne fourni pas l'algorithme sous-jacent.

Citation:

B(A==1) => Matlab travail seulement sur les valeur de B ayant les mêmes indices que les valeur égale à 1 dans A.

Soit, mais comment cela fonctionne-t-il algorithmiquement ? Est-ce que cela signifie pour tout i : si A(i) == 1 alors travailler sur B(i) ? je ne voit pas vraiment comment faire pour ne pas vérifier toutes les valeurs de A (donc naïvement faire une boucle sur A)...

Citation:

[...]elle exploite les qualités de Matlab, à savoir le travail vectoriel[...]

Faut que je regarde ce que cela signifie.

@Dut

Citation:

Il "suffit" de comparer les différents codes

And the winner is...
Sauf si j'ai fait une grossière erreur, il semble que MicBeastKiller_1 soit plus rapide pour de gros vecteurs...

Citation:

J'ai fait le calcu de k en dehors de MicBeastKiller_2 car la phrase suivante laisse entendre que le nombre de 1 dans A est connu d'avance.

Tout à fait, le vecteur A est fabriqué dans une autre partie donc on connait le nombre de 1.

Citation:

Maintenant, je n'ai trouvé aucune information concernant l'algorithme utilisé par la fonction MIN de MATLAB

C'est bien suite à d'infructueuses recherches que j'ai posé ma question. tant pis...

Merci encore de vos réponses

1 pièce(s) jointe(s)

Citation:

Envoyé par MicBeastKiller

And the winner is...

Moi :mrgreen:

Un fichier C-MEX tout bête :

Code:

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
#include "mex.h"
 
void mexFunction( int nlhs, mxArray *plhs[],
        int nrhs, const mxArray *prhs[]) {
 
    double *A, *B, *mini;
    mwSize i, n, ind;
 
    A = mxGetPr(prhs[0]);
    B = mxGetPr(prhs[1]);
 
    n = mxGetNumberOfElements(prhs[0]);
 
    plhs[0] = mxCreateDoubleScalar(0);
    mini = mxGetPr(plhs[0]);   
 
    ind = 0;
 
    while( (A[ind] != 1.0) &&  (ind < n) )
        ind += 1;
 
    mini[0] = B[ind];
 
    ind += 1;
 
    for(i=ind;i<n;i++)
        if( (A[i]==1) && (B[i]<mini[0]) )
            mini[0] = B[i];
 
}

A compiler comme ceci :

Code:

mex Dut.c

Code:

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
function test
 
kt = 1;
kn = 6;
 
for n = 10.^(3:kn)
 
    A = double(rand(n,1)>.3);
    k = sum(A);
 
    B = rand(n,1);
 
    t = zeros(1,20);
 
    for i=1:20
        tic
        mini = MicBeastKiller_1(A,B);
        t(i) = toc;
    end
 
    T(kt,1) = mean(t);
 
    for i=1:20
        tic
        mini = MicBeastKiller_2(A,B,k);
        t(i) = toc;
    end
 
    T(kt,2) = mean(t);
 
    for i=1:20
        tic
        mini = Youni92(A,B);
        t(i) = toc;
    end
 
    T(kt,3) = mean(t);
 
    for i=1:20
        tic
        mini = Dut(A,B);
        t(i) = toc;
    end
 
    T(kt,4) = mean(t);
 
    kt = kt+1;
end
 
figure
h = plot(T);
legend(h,{'MicBeastKiller_1' 'MicBeastKiller_2' 'Youni92' 'Dut'},'location','NorthWest')
set(gca,'xtick',1:kt-1,'xticklabel',num2str(10.^(3:kn).'))
xlabel('Taille du vecteur')
ylabel('Temps (s)')

Voir le graphique attaché au message ;)

23/09/2010, 11h55
Youni92

Félicitation :ccool:

On comprend qui est ici pour aider et qui est ici pour être aidé :D
23/09/2010, 11h58
MicBeastKiller

Merci beaucoup Dut, je vais garder cela sous le coude car pour le moment tout se passe en script.

Merci aussi à toi Youni92