Interfaces, implémentation bas niveau et POO

Comment utiliser cette page

Cette page complète les fiches déjà vues sur les piles, les files, les listes et les dictionnaires. Elle explique une autre façon de fabriquer une pile ou une file : avec un tableau de taille fixe et une position, plutôt qu'avec les méthodes toutes prêtes d'une liste Python. Elle explique aussi ce qu'est une interface (ou structure de données abstraite), et elle introduit la programmation orientée objet, avec l'exemple de la classe Point.

1. Vocabulaire à connaître avant de commencer

Chaque mot ci-dessous est utilisé exactement dans ce sens dans toute la page.

2. Les files : implémentation avec un tableau circulaire

La fiche Les files montre une file simplifiée, construite avec une liste Python (append et pop(0)). Cette section montre une autre implémentation, plus proche de la mémoire d'un ordinateur : un tableau de taille fixe, une position de tête, et un nombre d'éléments.

2.1 — Le triplet qui représente une file

On représente l'état d'une file d'attente à un bureau de vote, avec LEN_FILE = 10. Au départ, quatre électeurs (e1, e2, e3, e4) sont déjà dans la file : e3 et e4 sont aux cases 0 et 1, e1 et e2 sont aux cases 8 et 9, la tête est en position 8 (c'est e1 qui sera servi en premier).

2.2 — Trace pas à pas

2.3 — Les opérations primitives

2.4 — Code Python

LEN_FILE = 10

def creer_file():
    """Construit une file vide, de taille fixe LEN_FILE."""
    return {"tableau": ['_'] * LEN_FILE,
            "position_tete": 0,
            "nombre_element": 0}

def est_vide_file(file):
    """Renvoie True si la file ne contient aucun élément."""
    return file["nombre_element"] == 0

def premier_file(file):
    """Renvoie l'élément en tête de file, sans le retirer."""
    assert not(est_vide_file(file)), 'la file est vide'
    pos = file["position_tete"]
    return file["tableau"][pos]

def retirer_file(file):
    """Retourne la file mise à jour après la sortie de l'élément en tête."""
    assert not(est_vide_file(file)), 'la file est vide'
    pos = file["position_tete"]
    file["tableau"][pos] = '_'
    file["nombre_element"] -= 1
    file["position_tete"] = (file["position_tete"] + 1) % LEN_FILE
    return file

def ajouter_file(file, element):
    """Retourne la file mise à jour après l'ajout d'un élément en queue."""
    assert file["nombre_element"] < LEN_FILE, 'la file est pleine'
    pos = file["position_tete"]
    nb_element = file["nombre_element"]
    fin = (pos + nb_element) % LEN_FILE
    file["tableau"][fin] = element
    file["nombre_element"] += 1
    return file

2.5 — Complexité

• Les cinq opérations (creer_file, est_vide_file, premier_file, ajouter_file, retirer_file) sont toutes en O(1) : elles ne font jamais de boucle, seulement des calculs de position.
• C'est une différence importante avec la version simplifiée de la fiche Les files, où file.pop(0) coûte O(n) car Python doit décaler tous les éléments restants. Ici, il n'y a jamais de décalage : seule la position de la tête change.

3. Les piles : implémentation avec un tableau et une position de sommet

De la même façon, une pile peut être implémentée avec un tableau de taille fixe LEN_PILE et un entier indiquant la position du sommet. Par convention, une position de sommet égale à -1 signifie que la pile est vide.

3.1 — Trace pas à pas

On reprend l'exemple d'une pile d'assiettes a1, a2, a3, a4, a5, déjà empilées dans cet ordre (a1 tout en bas, a5 au sommet).

3.2 — Les opérations primitives

3.3 — Code Python

LEN_PILE = 10

def creer_pile():
    """Construit une pile vide, de taille fixe LEN_PILE."""
    return {"tableau": ['_'] * LEN_PILE,
            "position_sommet": -1}

def est_vide_pile(pile):
    """Renvoie True si la pile ne contient aucun élément."""
    return pile["position_sommet"] == -1

def sommet_pile(pile):
    """Renvoie l'élément au sommet de la pile, sans le retirer."""
    assert not(est_vide_pile(pile)), 'la pile est vide'
    return pile["tableau"][pile["position_sommet"]]

def empiler(pile, element):
    """Retourne la pile mise à jour après l'empilement d'un élément au sommet."""
    assert pile["position_sommet"] < LEN_PILE - 1, 'la pile est pleine'
    pile["tableau"][pile["position_sommet"] + 1] = element
    pile["position_sommet"] += 1
    return pile

def depiler(pile):
    """Retourne la pile mise à jour après le dépilement de son sommet."""
    assert not(est_vide_pile(pile)), 'la pile est vide'
    pile["tableau"][pile["position_sommet"]] = '_'
    pile["position_sommet"] -= 1
    return pile

3.4 — Complexité

• Les cinq opérations sont en O(1) : empiler et dépiler ne modifient qu'une seule case et un seul entier, sans jamais parcourir le tableau.
• C'est le même résultat que la version simplifiée de la fiche Les piles avec append et pop() : les deux implémentations d'une pile sont en O(1) pour toutes leurs opérations.

4. La liste vue comme une interface (structure de données abstraite)

4.1 — Définition

4.2 — Une implémentation avec des tuples imbriqués

On peut implémenter cette interface avec des tuples Python : la liste vide est représentée par None, et chaque élément ajouté « enveloppe » le reste de la liste dans un couple (valeur, reste_de_la_liste).

def creer_liste():
    return None

def ajouter_en_tete(x, L):
    return (x, L)

def tete(L):
    return L[0]

def queue(L):
    return L[1]

def est_vide(L):
    return L == None

4.3 — Trace pas à pas : construire la liste des voyelles

On construit la liste L2 = <'a' ; 'e' ; 'i' ; 'o' ; 'u' ; 'y' ; ∅> en ajoutant les voyelles en tête, en partant de la dernière voyelle de l'ordre alphabétique.

Pour accéder à la voyelle 'i', il faut retirer deux fois la tête (avec queue), puis lire la nouvelle tête :

4.4 — Fonctions récursives sur cette interface

def nombre_element(L):
    """Nombre d'éléments d'une liste : 0 si vide, sinon 1 + le nombre
    d'éléments de sa queue."""
    if est_vide(L):
        return 0
    else:
        return 1 + nombre_element(queue(L))

def val(i, L):
    """Élément de rang i (0 = tête), en avançant i fois avec queue."""
    assert not(i < 0 or i > nombre_element(L)), 'index hors limite'
    compteur = 0
    temp_liste = L
    while compteur < i:
        temp_liste = queue(temp_liste)
        compteur += 1
    return tete(temp_liste)

def est_dans(x, L):
    """Vrai si x est un élément de la liste L, faux sinon."""
    if est_vide(L):
        return False
    else:
        if x == tete(L):
            return True
        else:
            return est_dans(x, queue(L))

4.5 — Complexité

• nombre_element(L) et est_dans(x, L) parcourent la liste élément par élément : dans le pire des cas, il faut autant d'étapes que d'éléments dans la liste, soit une complexité en O(n).
• val(i, L) demande exactement i étapes pour atteindre l'élément de rang i.

5. La programmation orientée objet : classes et objets

5.1 — Vocabulaire

5.2 — Exemple : la classe Point

On définit une classe Point, pour manipuler des points dans un repère : deux attributs, abscisse et ordonnée, et une méthode deplace pour effectuer une translation.

5.3 — Trace pas à pas dans une console Python

5.4 — Code Python (classe complète, avec attribut couleur)

class Point:
    "Un point du plan muni d'un repère"

    # Méthode constructeur
    def __init__(self, x, y, col="#000000"):
        self.abscisse = x
        self.ordonne = y
        self.couleur = col          # couleur au format RVB, ex. "#FF00AA"

    # Méthode deplace : translate le point de (dx, dy)
    def deplace(self, dx, dy):
        self.abscisse += dx
        self.ordonne += dy

    # Méthode rotation180 : symétrique du point par rapport à l'origine
    def rotation180(self):
        self.abscisse, self.ordonne = -self.abscisse, -self.ordonne

    # Méthode pour représenter le point à l'affichage
    def __repr__(self):
        return f'({self.abscisse!r} ; {self.ordonne!r}) couleur : {self.couleur}'

5.5 — Récapitulatif vocabulaire

• Le type de données avec ses caractéristiques et ses actions possibles s'appelle une classe.
• Les caractéristiques (ou variables) de la classe s'appellent les attributs.
• Les actions possibles sur ces attributs s'appellent les méthodes.
• Un constructeur est une méthode obligatoirement présente dans une classe ; elle crée et initialise un objet de cette classe.

6. Le dictionnaire vu comme une interface

La fiche Les dictionnaires présente la syntaxe Python (parcours, get, items...). Cette section présente l'interface abstraite à l'origine des dictionnaires : ce que le dictionnaire doit faire, indépendamment de la façon dont Python l'implémente.

6.1 — Les opérations abstraites

6.2 — Pourquoi la recherche est-elle si rapide dans un dictionnaire ?

7. Points clés à retenir

• Une structure de données abstraite (une interface) est définie par ses opérations, pas par sa façon d'être stockée en mémoire : une même pile ou une même file peut être implémentée avec une liste Python, ou avec un tableau et des positions.
• Avec un tableau circulaire, une file en O(1) pour toutes ses opérations ne fait jamais de décalage : elle déplace uniquement la position de la tête, avec un modulo.
• La liste peut aussi être vue comme une interface récursive (tete, queue, ajouter_en_tete), implémentable avec des tuples imbriqués ; les piles et les files en sont des cas particuliers.
• En programmation orientée objet, une classe regroupe des attributs (les données) et des méthodes (les actions) ; self désigne l'objet sur lequel la méthode est appelée, et __init__ l'initialise à sa création.
• La recherche dans un dictionnaire est en O(1) grâce au hachage, alors qu'elle est en O(n) dans une liste : c'est l'un des principaux intérêts de cette structure.