Recherche dans une map constante

Marsh Posté le 05-07-2002 à 10:41:52

Bonjour,

Que pensez vous de ca ?

Dans mon code, je dois recuperer un nombre A en fonction d'un element B. Ex:
A -> B
(1,5) -> 3
(2,12) -> 7
(0, 3) -> -1
etc...

Bref, c'est une map dont les valeurs sont constantes. Pour mon programme, il faut que ca soit le plus rapide possible.
Le nombre d'elements de ma map va etre de l'ordre de 16/20. J'ai fait des tests (ca peut pas etre des tests en vraies conditions reelles de la vie...) avec:
- un vector et std::find pour trouver les elements
- une map
- un vector trie et une recherche dychotomique

conclusion:
- la map est plus rapide que le vector seulement si le nombre d'element est vraiment important
- la recherche dychotomique est la plus rapide, sauf quand le nombre d'element est tres petit (genre 8)

A ca, il faut rajouter que plus la comparaison entre deux elements prend du temps, plus les algos demandant un petit nombre d'evaluations sont avantages.

Bout de code:

Code :

template <class It, class T>
It my_find(It begin, It end, const T &val)
{
It real_end = end;
for(;;)
{
if (begin==end)
return real_end;
It it = begin+(end-begin)/2;
if (*it==val)
return it;
if (val<*it)
end = it;
else
begin = it+1;
}
}

Marsh Posté le 05-07-2002 à 10:41:52

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed

Name *

Email *

URL

Message *