Discussion :

[AirSounet]

Bonjour,

Voila j'ai en fait un type vector qui peut atteindre une très grande taille n.
A un moment je dois rechercher une valeur dans ce vector, et cela doit être effectue n fois.
Ce que je fais en ce moment est quelque chose de ce genre ou t est de type vector avec des doublons.

Code :

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

1
2
3
4
5
 
int a = 2;
for(int i = 0 ; i < n ; i++)
    if(t[i] == a)
      return i;

Cette recherche de valeur a une complexité O(n) et j'aimerais la baisser au mieux a un ordre O(1). J'ai vu qu'il y avait le type map mais je ne sais pas si c'est la solution optimale.

Je souhaiterais connaitre votre avis la dessus avant de me lancer.
Merci !

[TheGzD]

Si les valeurs de ton vecteur ne sont pas ordonnancées d'une certaine façon je ne vois pas trop comment tu pourrais réduire la complexité.

[David Fleury]

J'imagine que tout le monde aimerait faire du O(1)...

[oodini]

Les set et multiset on une fonction find() en O(n*log(n)).
Tu ne trouveras pas mieux.

[Flob90]

Tu peux obtenir une complexité d'accés moyenne en temps constant en utilisant une table de Hashage (unordered_set en C++2011 pas exemple). Il faut cependant qu'il existe une fonction de hashage pour tes objets.

Sinon tu peux peut-etre réduire ce temps de recherche si tu t'assures que ton vecteur reste trié par exemple, en appliquant un dichotomie la complexité devrait dimunué (logarithmique peut-etre, calcul à faire). A voir si le coup pour assurer ce trie tout le long du programme n'est pas trop élévé par rapport à l'utilisation d'une recherche linéaire.

Et enfin tu peux utiliser un conteneur associatif (typiquement set) qui t'assure un complexité logarithmique (et non quasi-linéaire, qui est moins bon que linéaire, comme l'a indiqué oodini). Et ca doit globalement revenir à utiliser un conteneur séquentiel en assurant en permanence qu'il est trié.

[AirSounet]

Je vous remercie pour vos conseils.
Je vais en tester quelques-uns et je vous tiens au courant