Discussion :

[MicBeastKiller]

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 :

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

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 :

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

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.

[Youni92]

Essais ça:

Code :

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

Minimum = min(B(A==1))

[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

[Youni92]

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

Code :

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

[C, I] = min(A);

Code :

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

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.

[Jerome Briot]

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

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
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 :

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
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 :

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

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 :

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

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.

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

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

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

[MicBeastKiller]

Merci beaucoup de vos réponses.

@Youni92 :

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.

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)...

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

Faut que je regarde ce que cela signifie.

@Dut

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...

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.

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

[Jerome Briot]

And the winner is...

Moi

Un fichier C-MEX tout bête :

Code C :

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
#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 :

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

mex Dut.c

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
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

[Youni92]

Félicitation

On comprend qui est ici pour aider et qui est ici pour être aidé

[MicBeastKiller]

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

Merci aussi à toi Youni92