[STL] Algorithme pour la valeur la plus fréquente d'un conteneur ?

Marsh Posté le 03-10-2007 à 14:40:13

Salut,

Je me demandais s'il existait un algorithme de la STL pour déterminer la valeur qui apparaît le plus souvent dans un vecteur ? Genre un truc qui pour {1,3,3,9,9,9,9,10,10} rendrait 9 (ou (9;4) tant qu'à faire...).

Merci, en attendant je vais essayer de faire ça avec mes petites mains...

NB: Si toute la liste des algorithmes est là, alors y'a pas... Mais ça me paraît court comme liste ?

Message cité 1 fois
Message édité par SkippyleGrandGourou le 03-10-2007 à 14:45:44

Reply

Marsh Posté le 03-10-2007 à 14:40:13

Reply

Marsh Posté le 03-10-2007 à 19:33:44

une astucieuse combinaison de std::unique_copy ret de std::count devrait faire l'affaire

Reply

Marsh Posté le 04-10-2007 à 11:52:43

Effectivement. Malheureusement (et ça semble logique), c'est environ 30 fois plus rapide de faire un truc comme :

Code :

float prev=0;
float offset=0;
int U = 0;
int V = 0;
for (vector<float>::iterator zz=tmp.begin(); zz!=tmp.end(); ++zz)
{
if (*zz==prev)
++U;
else
{
if (U>V)
{
offset = prev;
V = U;
}
U = 0;
}
prev=*zz;
}

que :

Code :

vector<float> result;
insert_iterator<vector<float> > ins(result,result.end());
unique_copy(tmp.begin(), tmp.end(), ins);
int T = 0;
float Tv = 0;
for (vector<float>::iterator m=result.begin(); m!=result.end(); ++m)
{
int N = count(tmp.begin(),tmp.end(),*m);
if (N>T)
{
T = N;
Tv = *m;
}
}

Donc exit la STL pour cette opération... :hello:
(À moins qu'il n'y ait plus astucieux, ce qui ne m'étonnerais guère... )

Reply

Marsh Posté le 04-10-2007 à 12:13:23

y a pas de exit STL: faut pas s'étonner. Pour implémenter l'algorithme A, tu utilises l'algorithme B, donc forcément c'est pas les mêmes perfs. Ton besoin est spécifique, donc y a pas. A toi d'etre plus intelligent et d'écrire une version générique

Reply

Marsh Posté le 04-10-2007 à 12:16:39

à implémenter avec un for_each, ça doit donner quelque chose de tranquil

Reply

Marsh Posté le 04-10-2007 à 13:14:06

for_each est obligatoire ici, sinon c'est pas la peine. Aprés, unique me parait mieux que unique_copy.

Reply

Marsh Posté le 17-10-2007 à 21:24:48

SkippyleGrandGourou a écrit :

Salut,

Je me demandais s'il existait un algorithme de la STL pour déterminer la valeur qui apparaît le plus souvent dans un vecteur ? Genre un truc qui pour {1,3,3,9,9,9,9,10,10} rendrait 9 (ou (9;4) tant qu'à faire...).

Merci, en attendant je vais essayer de faire ça avec mes petites mains...

NB: Si toute la liste des algorithmes est là, alors y'a pas... Mais ça me paraît court comme liste ?

Si ton tableau est déjà trié c qd meme pas sorcier :sarcastic:

---------------
Asus P5Q Pro | C2D E8400 3GHz@4GHz + Noctua NH-C12P | 2x2Go Patriot Extreme PC-8500 | GeForce GTX 460@Stock 1Go GLH | Crucial SSD M4 64Go Sata3

Reply

[STL] Algorithme pour la valeur la plus fréquente d'un conteneur ?

Sujets relatifs:

Leave a Replay