Algo pour quantiliser une valeur

Version imprimable

16/09/2008, 15h40
tnarol

Algo pour quantiliser une valeur

Salut,

J'ai un vecteur de valeurs, et une valeur particulière, je veux connaître le quantile (au sens de l'ensemble des valeurs du vecteur) auquel appartient ma valeur particulière. Je donne bien sûr le nombre de quantiles total.

Pour l'instant j'en suis à un algo qui classe le vecteur de valeurs puis qui va comparer la valeur particulière à chaque élément entre 0 et n jusqu'à ce que je trouve une valeur inférieure à la valeur particulière.

Est ce qu'il y a plus rapide tout en restant relativement simple ?
16/09/2008, 15h42
yan

Salut.
Pas tout compris...
Tu pourrais faire un exemples??

Peut être
http://r0d.developpez.com/articles/algos-stl/#LII-C-2
16/09/2008, 16h03
Invité(e)

Bonjour,

Citation:

Envoyé par tnarol

Est ce qu'il y a plus rapide tout en restant relativement simple ?

La dichotomie est en général assez rapide pour des comparaisons de ce genre.
16/09/2008, 16h50
tnarol

Citation:

Envoyé par Mongaulois

Salut.
Pas tout compris...
Tu pourrais faire un exemples??

Peut être
http://r0d.developpez.com/articles/algos-stl/#LII-C-2

Ben par exemple j'ai comme vecteur de valeurs {1,2,9,4,7,6,7,8}
Mettons que je veuille savoir dans quel quartile est la valeur 5
Les intervalles qui composent les quartiles sont des ensembles ordonnés de 2 valeurs car il y en a 8 au départ (8/4 = 2)
[1,2][4,6][7,7][8,9]
Ainsi présenté on voit que 5 est situé dans le 2ème quartile
-> 2 c'est la réponse que je veux.

En pratique c'est sûrement pas nécessaire d'avoir le découpage exact en quartiles pour connaitre la valeur finale...
16/09/2008, 17h10
yan

si tu n'est pas envie de tout triée, nth_element() me semble la bonne solution
http://r0d.developpez.com/articles/algos-stl/#LII-C-2

Cela va trié jusqu'à ce que l'élément nth soit à ça place si l'on continue le trie.
Tu te retrouve ainsi avec deux sous partie. Une inférieur à l'élément et une supérieur à l'élément (je ne sait plus comment se gère l'égalité).
std::distance te permet de connaitre la distance entre la position résultat et le début de ton tableau

Enfaite, peut être que std::partition est plus adapté
http://r0d.developpez.com/articles/algos-stl/#LII-B-12

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <limits>
using namespace std;
 
 
struct gen
{
    gen():i(0){}
	int operator()()
    {
		return i++ ;
    }
    int i;
};
 
 
 
int main(int argc, unsigned char* argv[])
{	
	srand(0);
 
    std::vector<int> m_vect(100);
    /*init vector*/
    std::generate(m_vect.begin(),m_vect.end(),gen());
    std::random_shuffle(m_vect.begin(),m_vect.end());
 
 
    std::vector<int>::iterator pos = std::partition
        (
        m_vect.begin(),
        m_vect.end(),
        bind2nd(less<int>(), 25)
        );
    std::cout<<std::distance(m_vect.begin(),pos)<<std::endl;
 
	return 0;
}

16/09/2008, 17h42
Bakura

Et si tu ajoutes ces valeurs dans un set, ce sera déjà trié, après l'accès aux valeurs sera sûrement plus lent qu'un vector mais le fait de ne pas le trier te permettra peut-être de gagner un peu.

ou un simple count_if

Code:

1
2
3
4
5
6
 int count = std::count_if
        (
        m_vect.begin(),
        m_vect.end(),
        std::bind2nd(std::less<int>(), 25)
        );

17/09/2008, 09h29
tnarol
Citation:
Envoyé par Mongaulois

ou un simple count_if

Code:

1 2 3 4 5 6 int count = std::count_if ( m_vect.begin(), m_vect.end(), std::bind2nd(std::less<int>(), 25) );
Oui merci c'est exactement ce que j'ai fini par trouver. Je crois que c'est le plus rapide.
17/09/2008, 09h33
3DArchi

Citation:

Envoyé par tnarol

Ben par exemple j'ai comme vecteur de valeurs {1,2,9,4,7,6,7,8}
Mettons que je veuille savoir dans quel quartile est la valeur 5
Les intervalles qui composent les quartiles sont des ensembles ordonnés de 2 valeurs car il y en a 8 au départ (8/4 = 2)
[1,2][4,6][7,7][8,9]
Ainsi présenté on voit que 5 est situé dans le 2ème quartile
-> 2 c'est la réponse que je veux.

En pratique c'est sûrement pas nécessaire d'avoir le découpage exact en quartiles pour connaitre la valeur finale...

C'est plus un problème de math que de STL. Si je comprend bien, tu part d'un ensemble N de cardinalité n, tu veux le découper en quantile de dimension q, et tu voudrais savoir à quel quantile appartient une valeur v. Sauf, que tu ne veux pas découper tout ton ensemble N pour cela.
Une façon de faire serait d'utiliser v comme pivot pour découper ton espace N entre ceux plus petit N1 et ceux plus grand N2. La borne inférieur de ton quantile sera donnée par le min des card(N1)%q max de N1 et le max par le max des min de card(N2)%(q-NbrElementDuQuantileCoteInferieur) de N2. Ou quelque chose de ce goût là à affiner plus précisément et en gérant les cas particulier (pivot < N ou pivot>N, cas triviaux).
17/09/2008, 09h45
yan

Si ton ensemble est trié, regarde peut être les recherche binaire
http://r0d.developpez.com/articles/algos-stl/#LII-C-3