Discussion :

[andromeda]

Bonjour,

Je voulais savoir si la fonction bsearch était plus performant qu'une recherche dans un tableau via un for ?

en gros est ce que:

Code :

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

1
2
3
4
5
6
 
 
for(int i = 0; i < count; i++)
{
   if (tab[i] == x) { trouve = true; break; } 
}

est moins performant qu'un bsearch.

Merci de votre aide.

[Trademark]

Salut,

La recherche linéaire (via boucle for) est moins performante car au maximum, tu parcourras tout ton tableau, donc la complexité est en O(n) – n étant le nombre d'élément dans le tableau. Une recherche binaire (binary search) est beaucoup plus rapide car tu ne parcourras au maximum que O(log(n)) éléments. Ce qui signifie que à chaque comparaison d'élément tu divises en deux ton espace de recherche. Si tu as 1000 éléments, seulement en regardant le milieu de ton tableau tu peux dire si tu vas aller dans la partie gauche ou droite (et donc virer 500 éléments qui ne correspondront pas à ta recherche).

Attention au fait qu'une recherche binaire ne peut se réaliser que dans un tableau préalablement trié ! Tandis que la recherche linéaire peut se faire dans un tableau non trié. Néanmoins, si tu fais beaucoup de recherche, il est avantageux de trier ton tableau avant de faire les recherches.

[andromeda]

merci pour ton explication.

[koala01]

Salut,

En fait, la réponse peut varier entre "oui si..." et "non car..." .

On peut en effet considérer que la rechercher dichotomique est plus efficace que la recherche incrémentielle si... le tableau est trié.

Dans ce cas, une recherche dichotomique aura une complexité en O(log(N)) (on parle de complexité logarithmique) alors que la recherche incrémentielle aura une complexité en O(N) (il faudra, au maximum, un nombre de tests équivalent au nombre d'éléments).

Mais on peut également estimer que la recherche dichotomique sera moins efficace que la recherche incrémentielle car, justement... le tableau doit être trié, et que le tri d'un tableau, ca prend du temps.

Si tu passes ton temps à ajouter et à retirer des éléments entre deux recherches, tu perdras très certainement à peu près autant de temps à trier ton tableau pour pouvoir effectuer ta recherche que tu n'en gagnera en effectuant une recherche dichotomique.

Par contre, si tu remplis ton tableau et que tu le tries " une bonne fois pour toutes " avant de faire tes recherches, tu observeras sans doute un gain de temps d'autant plus important que ton tableau contiendra un nombre (très) élevé d'éléments.

Cependant, il faut garder la phrase de Donald Knuth en tête:

Premature optimization is the root of all evil

(l'optimisation prématurée est la source de tous les maux)

et se dire que, tant que tu n'as pas pu prouver, par un profiling complet, que ton problème de performances vient bel et bien de la recherche incrémentielle, et, surtout, que tu gagneras en performances (une fois l'initialisation, qui prendra sans doute du coup plus longtemps, effectuée) en passant à une recherche dichotomique, la solution la plus simple reste toujours la moins compliquée (Heu, pardon, je veux dire la meilleure)

Il faut, enfin, se dire que le concept de tableau n'est, vraiment pas, le concept le plus intéressant lorsqu'il s'agit de travailler avec des données triées, et que le concept d'arbre binaire de recherche ( ou en anglais RBtree (pour RedBlackTree) ) est globalement mieux adapté, surtout s'il y a de fortes fluctuations au niveau du nombre d'éléments entre les recherches, et surtout si les éléments ne sont pas triés à l'origine.

Ce dernier concept (je parle du concept d'arbre binaire de recherche) est mis en oeuvre, en C++, par des classes comme le set ou la map (std::set et std::map, pour être précis), et tu aurais sans doute plus intérêt à envisager de te tourner vers l'une de ces classes qu'à envisager de mettre ton propre algorithme de recherche dichotomique sur un tableau au point

[EDIT] Enfin, garde toujours bien en tête le fait que la comparaison elle-même prend du temps et que le temps pris pour la faire dépend essentiellement du type de l'élément que tu veux comparer :

La comparaison sur des types primitifs est particulièrement rapide, car elle peut se limiter à une instruction processeur, alors que la comparaison de chaines de caractères prendra d'autant plus de temps que les chaines seront longues et proches l'une de l'autre, parce qu'il faudra un nombre de comparaison équivalent au nombre de caractères communs entre les deux chaines de caractères.

[andromeda]

en fait c'est un tableau qui contient a peu près 500 éléments fixe non trié, il n'y a pas d'ajout ni de suppression, et je vérifie si l'élément est contenu dans une chaine de caractère, dans ce cas je fait une action.

Actuellement je ne resent pas de perte en performance en C++, mais je me demandais si je pouvais l'améliorer avec les fonction bsearch.

si j'utilise bsearch je devrais trié le tableau à chaque fois car il n'est pas trié.

[koala01]

En fait, tu devras le trier une fois, si tu ne fais plus d'ajout ou de suppression une fois qu'il a été trié.

Si tu peux te contenter de trier une fois pour toutes ton tableau, avant de faire un grand nombre de recherches, la dichotomie peut valoir la peine, car ta recherche pourrait donner un résultat après seulement 9 comparaisons ( jusqu'à 511 éléments dans ton tableau, 10 jusqu'à 1023 éléments) par dichotomie contre potentiellement 500 et quelques comparaisons si l'élément recherché est "en fin de tableau" pour la recherche séquentielle.

Comme je te l'ai dit, tu peux aussi envisager d'utiliser une structure plus adaptée, comme std::set (ou std::map, selon tes besoins) qui offre la garantie que les éléments sont triés en permanence, et qui, de plus, présente l'énorme avantage de fonctionner avec des éléments non contigus en mémoire.

Ces structures présentent néanmoins un léger inconvénient dans le sens où l'ajout ou la suppression d'un élément est potentiellement plus lent que pour un tableau (bien que cela reste à démontrer, dans ta situation propre), de par la garantie de garder les éléments triés qu'elles offrent.

Comme nous ne connaissons pas exactement le contexte dans lequel tu te trouves, il nous est particulièrement difficile de donner une réponse ferme et définitive.

Tout ce que nous pouvons donc faire, c'est te donner des pistes afin de te permettre de choisir en connaissance de cause

Au passage, même si le schéma mériterait sans doute amplement une mise à jour, il existe une entrée de la FAQ qui te donne le cheminement à suivre pour déterminer la meilleure structure pour contenir tes objets

N'hésite pas à faire le test pour ta situation propre

[andromeda]

Merci pour tes explications, je vais étudier les différentes pistes.