Discussion :

[tnarol]

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 ?

[yan]

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

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

[Invité(e)]

Bonjour,

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.

[tnarol]

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

[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

[yan]

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

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
#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;
}

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

[yan]

ou un simple count_if

Code :

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

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

[tnarol]

ou un simple count_if

Code :

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

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.

[3DArchi]

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

[yan]

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