Chapitre 1: Parcours séquentiel d'un tableau

Dans ce chapitre, nous allons étudier des algorithmes de parcours séquentiel d'un tableau pour:

1. Rechercher un élément d'un type donné.
2. Rechercher le maximum d'un tableau.
3. Calculer la moyenne d'un tableau.

Ces algorithmes "séquentiels" ne sont pas du tout efficace, on les appelle en anglais "Brute force algorithms".

Méthodes de parcours séquentiel d'un tableau

avec les indices

On peut parcourir le tableau en utilisant les indices, pour cela on utise la fonction range qui génére des entiers successifs jusqu'à une limite supérieure ici la longueur totale de la liste.

L = [12, 24, 32, 69, 45, -12]
for i in range(len(L)):
    print("indice: ", i, "valeur: ", L[i])

indice:  0 valeur:  12
indice:  1 valeur:  24
indice:  2 valeur:  32
indice:  3 valeur:  69
indice:  4 valeur:  45
indice:  5 valeur:  -12

avec le mot-clé in

Python met à disposition le mot-clé in pour réaliser aisément des itérations sur les listes.

for e in L:
    print("élément: ", e)

élément:  12
élément:  24
élément:  32
élément:  69
élément:  45
élément:  -12

Recherche d'un extrémum

On initialise la valeur au premier élement du tableau puis on parcours le tableau pour vérifier s'il existe un élément soit plus petit soit plus grand.

Recherche du maximum

def maximum(liste):
    # ne pas utiliser max pour le nom de variable
    # car la fonction max existe en Python(on l'écraserait!)
    maxi = liste[0]
    for e in liste:
        if e > maxi:
            maxi = e
    return maxi

# appel de la fonction sur L
maximum(L)

69

Recherche du minimum

def minimum(liste):
    mini = L[0]
    for e in liste:
        if e < mini:
            mini = e
    return mini

# appel de la fonction avec la liste L en argument
minimum(L)

-12

Calculer la moyenne d'un tableau

On initialise une valeur accumulatrice à 0, puis on additionne tous les éléments du tableau. Enfin on divise la somme des éléments par le nombre d'éléments du tableau.

def moyenne(liste):
    somme = 0
    for e in liste:
        somme = somme + e
    # On divise la somme de tpus les éléments par leur nombre
    moyenne = somme / len(L)
    return moyenne

moyenne(L)

28.333333333333332

La recherche en table

Nous allons voir comment chercher une valeur dans un tableau par une méthode de parcours du tableau. Cet algorithme naïf est trsè couteux, et on verra par la suite d'autres algoritmes beaucoup plus efficaces pour rechercher un élément.

Commencons par créer une liste d'éléments

Pour cela nous allons écrire une fonction pour créer facilement des listes de mots.

import random
import string

lettres = string.ascii_lowercase

def create_liste(N, l=3):
    """Renvoie une liste de N mots ayant l lettres"""
    L = []
    # on rend le générateur prédictible en imposant une graine fixe
    random.seed(1789)
    for i in range(N):
        mot = ''.join(random.choice(lettres) for i in range(l))
        L.append(mot)
    return L
mots = create_liste(10, 3)
print(mots)

['xwt', 'bup', 'bou', 'xbd', 'upd', 'fuz', 'tfb', 'yht', 'ryd', 'twn']

Algorithme de recherche par parcours séquentiel du tableau

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.

Dans une fonction le return est définitif, on peut donc facilement arrêter la boucle dès que la valeur est trouvée. Si on est arrivé au bout de la boucle on est donc certains que l'élément cherché n'est pas présent.

def recherche(liste, cherche):
    """Fonction de recherche de l'élément dans la liste

    Arguments
    ---------
    l: liste
        la liste dans laquelle on cherche
    e: str
        l'élément chérché
    Retourne
    --------
    int 
       l'indice de l'élément si trouvé et moins la longeur de la liste -1  sinon
    """
    for e in liste:
        if e == cherche:
            return i
    return -len(liste) - 1

recherche(mots, "fuz")

5

recherche(mots, "ful")

-11

Coût de l'algorithme: notion de complexité

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é) parcourir toute la liste.

On dit que le coût de l'algorithme est linéaire ou encore que c'est un algorithme de complexité n, n étant la taille des données. En effet, l'algorithme effectue n tours de boucles pour trouver la solution dans le pire des cas.

Mesure du temps de référence(benchmark)

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

Remarque: on utilise des mots de 5 caractères ce qui permet d'obtenir $26^5$ mots différents(bien que le générateur puisse créer des doublons dans la liste).

mots = create_liste(int(1E7), 5)

%%timeit
recherche(mots, 'abcde')

129 ms ± 655 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

On voit qu'en moyenne, l'algorithme a pris environ 130ms pour effectuer cette recherche. On comparera ce temps au temps mis par un algorithme de recherche beaucoup plus efficace dans un chapitre ultérieur: la recherche dichotomique.