Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214

Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214

Comparaison de performances

Vous avez écrit une fonction de recherche séquentielle et une fonction de recherche dichotomique.

Nous allons comparer le temps d'exécution de ces fonctions.

Le module time contient des fonctions de mesure de temps. time_ns donne un temps écoulé en nanosecondes.

from random import randrange
from time import perf_counter_ns as chrono

# n'oubliez pas d'importer ou recopier vos fonctions
# recherche_sequentielle et recherche_dichotomique

# On va créer des tableaux de N items au hasard entre 0 et M
# On pourra changer la valeur de N
N = 1000
M = 100000
T = [randrange(M) for i in range(N)]
needle = randrange(M)

# cas séquentiel :
depart = chrono()
i = recherche_sequentielle(T, needle)
fin = chrono()
duree = fin - depart
print(f"recherche sequentielle renvoie {i} en {duree} ns.")

# cas dichotomique
depart = chrono()
T.sort()
fin = chrono()
duree = fin - depart
print(f"Le tri a nécessité {duree} ns.")

depart = chrono()
i = recherche_dichotomique(T, needle)
fin = chrono()
print(f"recherche dichotomique renvoie {i} en {duree} ns.")

Vous pouvez constater que la recherche dichotomique est beaucoup plus rapide mais elle nécessite de trier le tableau ce qui prend du temps. Tenant compte de ce coût supplémentaire, le tri dichotomique reste-t-il intéressant ?

Dans certains cas, le tableau est déjà trié pour d'autres raison. On n'a donc pas à faire le tri spécialement pour la recherche.
Si on a plusieurs recherches à faire, il peut être intéressant de faire le tri, une fois, ce qui permet de gagner du temps sur toutes les recherches à suivre.