Discussion :

[camboui]

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 !

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

[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" ?

[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

[yan]

Salut,
tu pourrai te faire un foncteur pour cela.

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

[camboui]

j'en suis


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

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

[yan]

j'en suis


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

Au moins tu as compris mon code

[yan]

EN faite, le foncteur n'est pas tellement necessaire ici. C'est vrai
mais bon je m'entraine

tu as beaucoup plus rapide pour initialiser ton set :

Code :

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

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

ou

Code :

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

1
2
3
4
5
6
std::set<int> s
.
.
.
s.clear();
s.insert(myvect.begin(),myvect.end());

[poukill]

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

Effectivement, un petit:

Code :

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

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

[yan]

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

Effectivement, un petit:

Code :

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

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

[poukill]

Plus je réfléchis, plus je me dis que tu as raison ...

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

[Alp]

Une version bien plus couteuse mais qui permet d'élargir ta connaissance des algorithmes standards se baserait sur std::count_if

[yan]

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

[poukill]

Effectivement, si le vector ne doit pas être modifié, il faudra en faire une copie, alors...

[camboui]

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

[yan]

Ah, enfin une réponse à ma question initiale 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

[JolyLoic]

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.