Python avancé

Navigation:: Boucles; Types composites; Algorithmes de tri; La dichotomie

La dichotomie

publié le jeu. 22 février 2018

Dans cette partie, nous allons illustrer la méthode de dichotomie sur l'exemple de la recherche d'un élément dans un tableau trié.

Nous verrons qu'il s'agit d'une méthode beaucoup plus efficace que le parcours complet du tableau. Elle fait partie des méthodes algorithmiques dites: "Diviser pour régner"

La recherche dichotomique, ou recherche par dichotomie, est un algorithme de recherche pour trouver la position d'un élément dans un tableau trié. Le principe est le suivant : comparer l'élément avec la valeur de la case au milieu du tableau ; si les valeurs sont égales, la tâche est accomplie, sinon on recommence dans la moitié du tableau pertinente. Source Wikipedia

Illustration de la recherche de l'élément 4 dans tableau trié.

Par Tushe2000 -- Template:LoStrangolatore, Domaine public, Lien

Commencons par créer une liste d'éléments triés¶

Pour cela nous allons écrire une fonction pour créer facilement des listes d'entiers successifs.

In [1]:

def create_liste_triée(N):
    """Renvoie une liste triée de N entiers entre 0 et N-1"""
    L = []
    for i in range(N):
        L.append(i)
    return L
triés = create_liste_triée(10)
print(triés)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

La recherche en table¶

Pour trouver un élément la méthode la plus simple consisterait à parcourir l'ensemble du tableau et de s'arrêter lorsqu'on trouve l'élément.

On peut par exemple écrire cet algorithme avec une boucle while.

In [2]:

cherché = 12
i = 0
while i < len(triés) and triés[i] != cherché:
    i += 1
    
if i < len(triés):
    print("Trouvé:", i)
else:
    print("Non trouvé")

Non trouvé

In [3]:

cherché = 7
i = 0
while i < len(triés) and triés[i] != cherché:
    i += 1
if i < len(triés):
    print("Trouvé:", i)
else:
    print("Non trouvé")

Trouvé: 7

Cette méthode a l'avantage d'ếtre simple, et fonctionne cependant si le tableau est long l'algorithme devient très long. Il faut dans le pire des cas(si l'élément cherché està la fin ou n'est pas trouvé) par courir toute la liste.

Remarque: On dit que c'est un algorithme de complexité n, n étant la taille des données. L'algorithme effectue n opérations dans le pire des cas.

Mesurons le temps pris par cet algorithme sur une liste de 10 millions d'éléments grâce à la fonction magique %timeit

In [4]:

%%timeit
triés = create_liste_triée(10000000)

cherché = 1E10
i = 0
while i < len(triés) and triés[i] != cherché:
    i += 1
if i < len(triés):
    print("Trouvé:", i)
else:
    print("Non trouvé")

Non trouvé
Non trouvé
Non trouvé
Non trouvé
1 loop, best of 3: 3.46 s per loop

On voit que dans le meilleur des trois cas l'algorithme a pris environ 3s pour effectuer cette boucle.

La dichotomie¶

Nous allons maintenant étudier l'algorithme de dichotomie. On peut comparer ça à une recherche dans un dictionnaire(qui a eu la bonne idée d'être trié!)

Nous allons commencer par le nombre au milieu de la liste, puis s'il ne s'agit pas de ce nombre, regarder s'il est supérieur ou inférieur au nombre chérché.

S'il est inférieur, on effectue une nouvelle comparaison au milieu de la première moitié du dictionnaire.
S'il est supérieur, on effectue la comparaison au milieu du deuxième dictionnaire.

Et ainsi de suite...

Voici un exemple d'implémentation:

In [5]:

cherché = 7
triés = create_liste_triée(10)

i = 0
j = len(triés)
while i < j:
    # On se place au milieu de la liste
    k = (i + j) // 2 # il, s'agit d'une division entière
    print("On cherche en ", k)
    if triés[k] == cherché:
        i = k
        j = k
    elif triés[k] < cherché:
        i = k
    else:
        j = k

if triés[i] == cherché:
    print("Trouvé:", triés[k])
else:
    print("Non trouvé")

On cherche en  5
On cherche en  7
Trouvé: 7

Incroyable on a trouvé en deux fois! Et si on ne trouve pas alors?

In [6]:

cherché = 11
i = 0
j = len(triés)
while i != j:
    # On se place au milieu de la liste
    k = (i + j) // 2 # il, s'agit d'une division entière
    print("On cherche en ", k)
    if triés[k] == cherché:
        i = k
        j = k
    elif triés[k] < cherché:
        i = k + 1
    else:
        j = k - 1

if i < len(triés):
    print("Trouvé:", triés[i])
else:
    print("Non trouvé")

On cherche en  5
On cherche en  8
On cherche en  9
Non trouvé

Incroyable on a trouvé en trois fois seulement. Il s'agit d'un logarithme ayant une compléxité en $log_2 (n)$.

Par exemple:

si n= 10: $log_2 (10) = 3.3$.
si n= 1E7: $log_2 (10 000 000) = 23$.

Au lieu de 10 millions d'opérations, on en effectue 23!

Mesurons le temps de recherche pour un élément trouvé et pour un élément non trouvé.

In [7]:

%%timeit
triés = create_liste_triée(10000000)

cherché = 13
i = 0
j = len(triés)
while i != j:
    # On se place au milieu de la liste
    k = (i + j) // 2 # il, s'agit d'une division entière
    print("On cherche en ", k)
    if triés[k] == cherché:
        i = k
        j = k
    elif triés[k] < cherché:
        i = k + 1
    else:
        j = k - 1

if i < len(triés):
    print("Trouvé:", triés[i])
else:
    print("Non trouvé")

On cherche en  5000000
On cherche en  2499999
On cherche en  1249999
On cherche en  624999
On cherche en  312499
On cherche en  156249
On cherche en  78124
On cherche en  39061
On cherche en  19530
On cherche en  9764
On cherche en  4881
On cherche en  2440
On cherche en  1219
On cherche en  609
On cherche en  304
On cherche en  151
On cherche en  75
On cherche en  37
On cherche en  18
On cherche en  8
On cherche en  13
Trouvé: 13
On cherche en  5000000
On cherche en  2499999
On cherche en  1249999
On cherche en  624999
On cherche en  312499
On cherche en  156249
On cherche en  78124
On cherche en  39061
On cherche en  19530
On cherche en  9764
On cherche en  4881
On cherche en  2440
On cherche en  1219
On cherche en  609
On cherche en  304
On cherche en  151
On cherche en  75
On cherche en  37
On cherche en  18
On cherche en  8
On cherche en  13
Trouvé: 13
On cherche en  5000000
On cherche en  2499999
On cherche en  1249999
On cherche en  624999
On cherche en  312499
On cherche en  156249
On cherche en  78124
On cherche en  39061
On cherche en  19530
On cherche en  9764
On cherche en  4881
On cherche en  2440
On cherche en  1219
On cherche en  609
On cherche en  304
On cherche en  151
On cherche en  75
On cherche en  37
On cherche en  18
On cherche en  8
On cherche en  13
Trouvé: 13
On cherche en  5000000
On cherche en  2499999
On cherche en  1249999
On cherche en  624999
On cherche en  312499
On cherche en  156249
On cherche en  78124
On cherche en  39061
On cherche en  19530
On cherche en  9764
On cherche en  4881
On cherche en  2440
On cherche en  1219
On cherche en  609
On cherche en  304
On cherche en  151
On cherche en  75
On cherche en  37
On cherche en  18
On cherche en  8
On cherche en  13
Trouvé: 13
1 loop, best of 3: 895 ms per loop

Il nous a fallu moins d'une seconde cette fois-ci.

Voyons si l'élément est non trouvé.

In [8]:

%%timeit
triés = create_liste_triée(10000000)

cherché = 1E9
i = 0
j = len(triés)
while i != j:
    # On se place au milieu de la liste
    k = (i + j) // 2 # il, s'agit d'une division entière
    print("On cherche en ", k)
    if triés[k] == cherché:
        i = k
        j = k
    elif triés[k] < cherché:
        i = k + 1
    else:
        j = k - 1

if i < len(triés):
    print("Trouvé:", triés[i])
else:
    print("Non trouvé")

On cherche en  5000000
On cherche en  7500000
On cherche en  8750000
On cherche en  9375000
On cherche en  9687500
On cherche en  9843750
On cherche en  9921875
On cherche en  9960938
On cherche en  9980469
On cherche en  9990235
On cherche en  9995118
On cherche en  9997559
On cherche en  9998780
On cherche en  9999390
On cherche en  9999695
On cherche en  9999848
On cherche en  9999924
On cherche en  9999962
On cherche en  9999981
On cherche en  9999991
On cherche en  9999996
On cherche en  9999998
On cherche en  9999999
Non trouvé
On cherche en  5000000
On cherche en  7500000
On cherche en  8750000
On cherche en  9375000
On cherche en  9687500
On cherche en  9843750
On cherche en  9921875
On cherche en  9960938
On cherche en  9980469
On cherche en  9990235
On cherche en  9995118
On cherche en  9997559
On cherche en  9998780
On cherche en  9999390
On cherche en  9999695
On cherche en  9999848
On cherche en  9999924
On cherche en  9999962
On cherche en  9999981
On cherche en  9999991
On cherche en  9999996
On cherche en  9999998
On cherche en  9999999
Non trouvé
On cherche en  5000000
On cherche en  7500000
On cherche en  8750000
On cherche en  9375000
On cherche en  9687500
On cherche en  9843750
On cherche en  9921875
On cherche en  9960938
On cherche en  9980469
On cherche en  9990235
On cherche en  9995118
On cherche en  9997559
On cherche en  9998780
On cherche en  9999390
On cherche en  9999695
On cherche en  9999848
On cherche en  9999924
On cherche en  9999962
On cherche en  9999981
On cherche en  9999991
On cherche en  9999996
On cherche en  9999998
On cherche en  9999999
Non trouvé
On cherche en  5000000
On cherche en  7500000
On cherche en  8750000
On cherche en  9375000
On cherche en  9687500
On cherche en  9843750
On cherche en  9921875
On cherche en  9960938
On cherche en  9980469
On cherche en  9990235
On cherche en  9995118
On cherche en  9997559
On cherche en  9998780
On cherche en  9999390
On cherche en  9999695
On cherche en  9999848
On cherche en  9999924
On cherche en  9999962
On cherche en  9999981
On cherche en  9999991
On cherche en  9999996
On cherche en  9999998
On cherche en  9999999
Non trouvé
1 loop, best of 3: 912 ms per loop

A nouveau on effectue les 23 itérations en moins d'une seconde. Voila pourquoi la dichotomie est une méthode si puissante.

Conclusion¶

Nous avons vu sur cet exemple en quoi la recherche dichotomique était une méthode efficace pour rechercher un élément dans un tableau trié.

Cela nous a permis d'introduire la notion de complexité d'un algorithme qui vise à évaluer l'efficacité des algorithmes en mesurant le nombre d'opérations nécessaires à la finalisation d'un algorithme.

Cette méthode n'est qu'un exemple de nombreux autres algorithmes utilisant une méthode générale appelée "Diviser pour régner"(Divide and conquer en anglais).

En informatique, diviser pour régner (du latin « Divide ut imperes », divide and conquer en anglais) est une technique algorithmique consistant à :

Diviser : découper un problème initial en sous-problèmes ;

Régner : résoudre les sous-problèmes (récursivement ou directement s'ils sont assez petits) ;

Combiner : calculer une solution au problème initial à partir des solutions des sous-problèmes.

Par Fschwarzentruber — Travail personnel, CC BY-SA 4.0, Lien

Cette technique fournit des algorithmes efficaces pour de nombreux problèmes, comme la recherche d'un élément dans un tableau trié (recherche dichotomique), le tri (tri fusion, tri rapide), la multiplication de grands nombres (algorithme de Karatsuba) ou la transformation de Fourier discrète (transformation de Fourier rapide). Source Wikipedia)

Matière: isn Mots-clés: python algorithmes de recherche dichotomie