Compter le nombre de valeurs unqiues

Version imprimable

28/11/2007, 12h31
camboui

Compter le nombre de valeurs unqiues

Je cherche à compter un nombre de valeurs uniques (les données d'origine sont dans un tableau de tableaux, 2 std::vector<> imbriqués quoi).

Je me propose très simplement de créer un std::set<> en parcourant mon tableau puis en lire la taille.

Y-a-t-il mieux, plus performant ? Par exemple, créer un std::vector<>, le trier, puis compter les valeurs uniques.

Merci !
28/11/2007, 13h33
r0d

Bonjour,

Que veux-tu dire par "valeur unique" ?
Sinon, tu peux jeter un coup d'oeil du côté de la fonction std::unique (en-tête <algorithm>, cf. lien dans ma signature).
28/11/2007, 13h47
camboui

5, 2, 3, 5, 4, 2, 4, 7, 1

Distinctes si tu préfères. Dans cet exemple il y a 6 valeurs distinctes parmi un total de 9.

std::unique(), je vais regarder.
Ceci dit, l'usage de std::set<> est une solution comme je le disais, mais est-ce "bien" ?
28/11/2007, 14h04
camboui

Je viens de voir std::unique(). Il en fait trop dans mon cas, j'ai juste besoin de les compter. La modification éventuel ajoute en complexité inutile.
Mais c'est une fonction intéressante à retenir (sauf que conserver le tri, indispensable avant l'appel de la fonction, n'eut pas été surperflu en sortie).

PS:
Dans ta documentation sur <algorithm> (très intéressante d'ailleurs) tu ne parles pas des fonctions "heap". Un petit tuto à leur sujet serait pas mal ;)

Salut,
tu pourrai te faire un foncteur pour cela.

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
 
#include <algorithm>
#include <iostream>
#include <vector>  
 #include <set>  
 
template <class T>
struct CombienUnique
	{
	CombienUnique(){};
	//constructeur par recopie bidon qui eviter de recopier le set.
	//swap les contenu des set
	CombienUnique(CombienUnique<T> & CU)
		{
		std::swap(myUnique,CU.myUnique);
		}
	void operator()(const T & t) {myUnique.insert(t);}
	int GetNbUnique() {return myUnique.size();};
 
	std::set<T> myUnique;
};
 
int main(int argc, char** argv)
{
//initialisation
std::vector<int> myvect;
myvect.push_back(1);
myvect.push_back(4);
myvect.push_back(10);
myvect.push_back(1);
myvect.push_back(20);
myvect.push_back(1);
myvect.push_back(10);
 
//récupère les uniques
CombienUnique<int> myFoncteur = std::for_each(myvect.begin(),myvect.end(),CombienUnique<int>());
//affichage
std::cout<<"Nb unique : "<<myFoncteur.GetNbUnique()<<std::endl;
std::copy(myFoncteur.myUnique.begin(),myFoncteur.myUnique.end(),std::ostream_iterator<int> (std::cout,"\n"));
 
return 0;
}

8O j'en suis :aie:
:king:

Bon, en attendant d'approfondir <algorithm> je vais me contenter d'un plus classique

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
int main(int argc, char** argv)
{
//initialisation
std::vector<int> myvect;
myvect.push_back(1);
myvect.push_back(4);
myvect.push_back(10);
myvect.push_back(1);
myvect.push_back(20);
myvect.push_back(1);
myvect.push_back(10);
 
//récupère les uniques
std::set<int> s;
{
for (std::vector<int>::iterator it=myvect.begin();it!=myvect.end();it++)
	s.insert(*it);
}
//affichage
cout<< "Nb unique : " << s.size() << endl;
{
for (std::set<int>::iterator it=s.begin();it!=s.end();it++)
	cout << *it << endl;
}
 
return 0;
}

28/11/2007, 14h56
yan

Citation:

Envoyé par camboui

8O j'en suis :aie:
:king:

Bon, en attendant d'approfondir <algorithm> je vais me contenter d'un plus classique

Au moins tu as compris mon code :king:
29/11/2007, 09h16
yan
EN faite, le foncteur n'est pas tellement necessaire ici. C'est vrai :aie:
mais bon je m'entraine

tu as beaucoup plus rapide pour initialiser ton set :
Code:

1 2 std::set<int> s(myvect.begin(),myvect.end());
ou
Code:

1 2 3 4 5 6 std::set<int> s . . . s.clear(); s.insert(myvect.begin(),myvect.end());
29/11/2007, 10h20
poukill
Je vois que tu t'éclates avec les foncteurs MonGaulois ! :mouarf:

Effectivement, un petit:
Code:

1 2 std::set<int> s(myvect.begin(),myvect.end()); std::cout << s.size() << std::endl;
permet de compter les uniques...
Ce ne sera pas l'algo le plus rapide, mais au moins ça marche bien ! :-)
29/11/2007, 10h26
yan
Citation:
Envoyé par poukill

Je vois que tu t'éclates avec les foncteurs MonGaulois ! :mouarf:

Effectivement, un petit:

Code:

1 2 std::set<int> s(myvect.begin(),myvect.end()); std::cout << s.size() << std::endl;

permet de compter les uniques...
Ce ne sera pas l'algo le plus rapide, mais au moins ça marche bien ! :-)
ben, en y réfléchissant je ne voit pas comment faire plus rapide....
29/11/2007, 10h30
poukill

Plus je réfléchis, plus je me dis que tu as raison ... :aie:
29/11/2007, 21h04
JolyLoic

Si on ne travaille pas par ajout successifs, en incrémental, mais une seules fois sur un bloc de données, et que les données sont légères, comme ici, je suis parès à parier qu'un sort sur un vector suivi d'un parcours pour compter sera plus rapide qu'une copie dans un set. Ne serait-ce que parce que la localité de la mémoire est meilleure.
29/11/2007, 21h07
Alp

Une version bien plus couteuse mais qui permet d'élargir ta connaissance des algorithmes standards se baserait sur std::count_if
29/11/2007, 21h59
yan

Citation:

Envoyé par JolyLoic

Si on ne travaille pas par ajout successifs, en incrémental, mais une seules fois sur un bloc de données, et que les données sont légères, comme ici, je suis parès à parier qu'un sort sur un vector suivi d'un parcours pour compter sera plus rapide qu'une copie dans un set. Ne serait-ce que parce que la localité de la mémoire est meilleure.

peut etre sur un petit vector. mais aprés...
Je sais pô.
Toute facon il me semble qu'il ne veut pas modifier sont vector :P
30/11/2007, 08h12
poukill

Effectivement, si le vector ne doit pas être modifié, il faudra en faire une copie, alors... :aie: ;)
03/12/2007, 13h17
camboui

Citation:

Envoyé par JolyLoic

Si on ne travaille pas par ajout successifs, en incrémental, mais une seules fois sur un bloc de données, et que les données sont légères, comme ici, je suis parès à parier qu'un sort sur un vector suivi d'un parcours pour compter sera plus rapide qu'une copie dans un set. Ne serait-ce que parce que la localité de la mémoire est meilleure.

Ah, enfin une réponse à ma question initiale 8-) Y-a-t-il mieux qu'utiliser un std::set<> ?

Pour rappel, je dois initialiser les valeurs du set/vector une par une. Lisez mon premier post, les donnés d'origine sont dans un tableau de tableaux (et pas nécessairement de même longueur).

Je peux vous donner le problème à la base :bug:
J'ai un graphe duquel j'extrais plusieurs chemins entre deux sommets. Jusqu'à présent les clients paient le nombre total de sommets visités par l'ensemble des chemins. Bien sur, de nombreux sommets se retrouvent dans plusieurs chemins différents et les clients ne veulent pas payer pour tous ces doublons. Je dois donc connaitre le nombre de sommets uniques de l'ensemble des chemins. Le tableau de tableaux est donc un tableau de chemins, chaque chemin étant un tableau de sommets.

Voilà, voilà, à vos méninges sachant que j'ai deux solutions proposées jusqu'à présent:
1) insertion des sommets un par un dans un std::set, puis size().
2) insertion des sommets un par un dans un std::vector, puis sort() et comptage.
:king:
03/12/2007, 13h56
yan

Citation:

Envoyé par camboui

Ah, enfin une réponse à ma question initiale 8-) Y-a-t-il mieux qu'utiliser un std::set<> ?

Sa methode est dans le cas ou le vector est déjà initialisé.
Sinon ben le set gagne. J'en suis quasi sur
03/12/2007, 18h30
JolyLoic

Citation:

Envoyé par Mongaulois

Sa methode est dans le cas ou le vector est déjà initialisé.
Sinon ben le set gagne. J'en suis quasi sur

Le seul point dont je suis quasi sur, c'est que seule une mesure (de préférence avec un jeu de données proche du jeu réel) permettra de départager les solutions.

Maintenant, sur le plan feeling et devinette et discussion de comptoir, je ne vois rien à l'avantage de set dans la description du problème. Là il en aurait certainement, c'est s'il fallait par exemple ajuster souvent le coût en ajoutant un nouveau trajet à ceux pris en compte.