====== Comparaison de performances ======

Vous avez écrit une fonction de [[nsi:premiere:tableau:recherche:sequentielle|recherche séquentielle]] et une fonction de [[nsi:premiere:tableau:recherche:dichotomie|recherche dichotomique]].

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

<WRAP>Le module ''time'' contient des fonctions de mesure de temps. ''time_ns'' donne un temps écoulé en nanosecondes.</WRAP>

<code python>
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.")
</code>

<WRAP tip>
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.
</WRAP>