Nous allons comparer l'efficacité d'une recherche naïve avec la recherche dichotomique, dans le cas d'un tableau trié.
Nous allons donc commencer par programmer les deux algorithmes. Puis, à l'aide d'une fonction générant aléatoirement des tableaux triés, nous comparerons le temps de calcul mis par chacune des fonctions.
Exercice 1
Compléter le code de la fonction recherche_naive qui prend en paramètres une valeur val et un tableau tab, et qui renvoie l'indice d'une occurrence de val dans tab, si elle est dans le tableau, et None sinon.
La recherche se fera de façon naïve, élément par élément.
Compléter le code de la fonction recherche_dichotomique qui prend en paramètres une valeur val et un tableau tabtrié dans l'ordre croissant, et qui renvoie l'indice d'une occurrence de val dans tab, si elle est dans le tableau, et None sinon. On fera la recherche en utilisant la dichotomie.
Compléter le code de la fonction genere_tableau qui prend en paramètres deux entiers positifs n et saut_max et qui renvoie un tableau, généré aléatoirement, de n entiers triés dans l'ordre croissant et dont l'écart entre 2 valeurs consécutives est comprise entre 0 et saut_max inclus. La première valeur est également entre 0 et saut_max.
Rappel sur les tirages aléatoires d'entiers
On rappelle que la fonction randint du module random permet de choisir un entier au hasard compris entre les deux paramètres a et b inclus.
tab est le tableau dans lequel faire la recherche.
recherche est la fonction de recherche (recherche_naive ou recherche_dichotomique).
k correspond au nombre de fois où on va chercher une valeur pour faire une moyenne de temps de calcul.
pire_cas qui permet de déterminer si on prend une valeur au hasard (False) ou une valeur qui n'est pas dans le tableau (True), ce qui garanti qu'on fera le nombre maximal d'essais pour les deux fonctions.
On fait la moyenne des temps mis par les k essais afin de lisser les éventuels anomalies.
Le module time
Le module time permet de faire des mesures de temps. La fonction time.time() renvoie le nombre de secondes écoulées depuis Epoch, qui est le 1e janvier 1970 pour les systèmes Unix et la plupart des langages de programmation.
En faisant la différence entre deux instants, on obtient le temps qui s'est écoulé entre ces deux instants, en secondes.
Ensuite, pour comparer les deux fonctions, on utilise la fonction suivante :
defcomparaison_temps(taille,k=100,pire_cas=False,saut_max=5):tab=genere_tableau(taille,saut_max)temps_naif=mesure_temps_recherche(tab,recherche_naive,k,pire_cas)temps_dichotomie=mesure_temps_recherche(tab,recherche_dichotomique,k,pire_cas)print(f"Pour chercher dans un tableau de taille {taille} :")print(f"Recherche naive : {temps_naif}")print(f"Recherche dicho : {temps_dichotomie}")
Exercice 4
Utiliser le programme suivant pour comparer les deux fonctions de recherche (qui sont en mémoire). Vous pouvez essayer avec des tableaux de longueur 100, 10000 et 1000000, que ce soit dans le pire des cas ou pas. Pour les grandes valeurs de taille, vous pouvez (et devriez) réduire la valeur de k.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Évaluations restantes : ∞/∞
Visualiser l'évolution du temps de recherche
Afin de visualiser l'évolution du temps de recherche en fonction de la taille du tableau, nous allons utiliser la fonction suivante :
importmatplotlib.pyplotaspltdefgraphique_temps(n_max,k,points=10,pire_cas=False,saut_max=5):t_taille=[]# pour les abscisses# Tableaux des ordonnéest_naif=[]t_dicho=[]pas=n_max//points# intervalle entre 2 tailles de tableaux à testern=pasfor_inrange(points):t_taille.append(n)# temps de calcul pour un tableau de taille ntab=genere_tableau(n,saut_max)temps_naif=mesure_temps_recherche(tab,recherche_naive,k,pire_cas)temps_dichotomie=mesure_temps_recherche(tab,recherche_dichotomique,k,pire_cas)# On rajoute les temps moyens aux listes des ordonnéest_naif.append(temps_naif)t_dicho.append(temps_dichotomie)n=n+pas# affichage des courbesplt.plot(t_taille,t_naif,label="naïf")plt.plot(t_taille,t_dicho,label="dichotomie")plt.legend()plt.show()
Les paramètres sont les suivants :
n_max est la taille maximale des tableaux ;
k correspond au nombre de répétitions à faire pour calculer la moyenne de temps pour chaque taille ;
points correspond au nombre de tailles différentes à tester entre 0 et n_max.
pire_cas permet d'indiquer si on veut se placer dans le pire des cas ou pas.
saut_max correspond à l'écart maximal entre deux valeurs dans les tableaux.
Exercice 5
En utilisant la fonction graphique_temps, visualiser l'évolution du temps de calcul avec la taille du tableau. Vous pouvez augmenter n_max ou mettre à vrai pire_cas. Par contre, il faut bien penser que plus n_max sera grand, plus le temps de calcul sera grand. Vous pouvez diminuer la valeur de k si le temps de calcul devient trop grand.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
# Tests
(insensible à la casse)(Ctrl+I)