Depuis hier j'ai un problème en voulant comparer les temps d'éxécutions entre la recherche séquentielle et dichotomique.
Pour un code strictement identique, sur python et sur une large gamme de jeux de tests, la recherche dichotomique est plus rapide que la recherche séquentielle (logique jusqu'ici), mais en c++, l'inverse se produit et je n'ai aucune idée de la source d'une telle inversion
Voici le code c++ :
#include <iostream>
#include <vector>
#include <time.h>
// Initialisation
void init(std::vector<int> &vect, int taille){
for(int i = 0; i < taille; i++){
vect.push_back(i+1);
}
}
void afficher(std::vector<int> vect){
for(int i = 0; i < vect.size(); i++){
std::cout << i << ") " << vect[i] << std::endl;
}
}
// Recherche
int recherche(std::vector<int> vect, int val){
int pos = -1;
int i = vect.size()-1;
bool trouve = false;
while(trouve == false && i >= 0){
if(vect[i] == val){
trouve = true;
pos = i;
}
i--;
}
return pos;
}
int dicho_rec(std::vector<int> vect, int deb, int fin, int val){
int res;
if(deb > fin){
res = -1;
} else {
int milieu = (deb + fin)/2;
if(vect[milieu] == val){
res = milieu;
} else if(vect[milieu] > val){
res = dicho_rec(vect, deb, milieu-1, val);
} else {
res = dicho_rec(vect, milieu+1, fin, val);
}
}
return res;
}
int recherche_dichotomique(std::vector<int> vect, int val){
return dicho_rec(vect, 0, vect.size(), val);
}
int main(){
std::vector<int> vecteur;
clock_t t1, t2;
float temps1, temps2;
int val;
bool test;
init(vecteur, 20000);
//afficher(vecteur);
val = 15000;
t1 = clock();
std::cout << recherche_dichotomique(vecteur, val) << std::endl;
t2 = clock();
temps1 = (float)(t2 - t1)/CLOCKS_PER_SEC;
std::cout << "Temps dichotomie : " << temps1 << std::endl;
t1 = clock();
std::cout << recherche(vecteur, val) << std::endl;
t2 = clock();
temps2 = (float)(t2 - t1)/CLOCKS_PER_SEC;
std::cout << "Temps séquentielle : " << temps2 << std::endl;
return 0;
}
Quand tu benchs, il faut faire attention à ne pas faire n'importe quoi. Par exemple, si tu ne recrées pas ton vecteur, il est dans les caches, au deuxième usage, ce qui peut augmenter la vitesse . Ensuite, un tableau de 15000 valeurs, c'est minuscule, du coup les temps d'accès sont vraiment très courts. Ensuite, si tu ne tests qu'une possibilité tu peux très bien tomber sur un cas désavantageux, il faut changer les valeurs, etc. Et avoir des choses un maximum aléatoire.
Finalement ici, tu fais des appels par valeurs dans une récursion, ça veut dire des copies dans tous les sens, d'où des performances qui s'écroulent. Passe ton tableau par référence, tu vas voir que ça se comporte mieux. Note aussi qu'écrire cette recherche récursivement est inutile, ça s'écrit très bien en séquentiel et ce sera tout aussi clair.
Dernière note. Ceci :
int milieu = (deb + fin)/2;
est une mauvaise formule pour calculer le milieu : tu peux déborder de ton entier si deb et fin sont trop grands.
En passant par référence la problème à été résolu, j'avais oublié les copies à chaque appel récursif
Alors oui pour la taille du vecteur, c'étais juste à titre d'exemple, en considérant la convergence asymptotique de la recherche dichotomique il est évident qu'un tableau de grande taille permet de mieux apprécier les différences.
Quant aux jeux de tests, j'avais créer une fonction rand pour l'occasion mais je l'avais supprimé ici pour plus de clarté.
Pour la version récursive, c'est surtout une question d'entrainement, j'essaye de m'habituer à écrire et à comprendre la récursivité
Par contre je suis entièrement d'accord pour le dernier point, quelle solution aurait tu à me proposer pour le calcul du milieu ?
Le problème ne vient absolument pas de la récursion, mais du passage du vecteur par copie dans la recherche par dichotomie
int dicho_rec(std::vector<int> vect, int deb, int fin, int val);
qui fait que le temps d'exécution d'une recherche est en n log n, évidemment pire que la recherche linéaire.
A remplacer d'urgence par un passage par référence (constante, qui plus est).
int dicho_rec(const std::vector<int> & vect,
int deb, int fin,
int val){
a partir de là, ça devrait aller plus vite que la recherche linéaire à partir de quelques dizaines d'élements.
D'autant que pour la récursion, le compilateur détecte parfaitement qu'il s'agit d'une récursion terminale, et génére une boucle comme un grand. Il fait ça très bien tout seul, préservons la simplicité d'expression.
Effectivement le problème venait du passage du vecteur en paramètre et des copies inutiles à chaque exécution de la fonction.
Merci pour vos réponses !
Problème recherche dichotomique
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Posez vos questions ou discutez informatique, sur le Discord NaN | Tuto : Preuve de programmes C
Posez vos questions ou discutez informatique, sur le Discord NaN | Tuto : Preuve de programmes C