Types et structures de données abstraites

Cours complet · informatique (MP2I/MPI), chapitre 6 · MP2I et MPI

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

6.1 L'algorithme et sa structure vont ensemble

Le programme ouvre sa partie « Structures de données » par une phrase qui vaut programme à elle seule : « on insiste sur le fait que le développement d'un algorithme va de pair avec la conception d'une structure de données taillée à la mesure du problème que l'on cherche à résoudre et des opérations sur les données que l'on est amené à répéter ».

L'idée est simple et elle décide de tout. Chercher un élément coûte $O (n)$ dans un tableau non trié, $O (lo g n)$ dans un tableau trié, $O (1)$ en moyenne dans une table de hachage. Ce n'est pas l'algorithme de recherche qui change : c'est la structure. Choisir sa structure, c'est déjà avoir écrit la moitié de son algorithme.

6.2 Les types du langage

6.2.1 Types prédéfinis, types composés, types paramétrés

Définition 6.1Trois familles

Prédéfini : booléen, entier, flottant, caractère. La brique de base.
Composé : plusieurs valeurs regroupées — struct en C, enregistrement ou n-uplet en OCaml.
Paramétré : un type qui en attend un autre pour être complet. Le tableau en est l'exemple du programme : 'a array n'est pas un type, int array en est un.

Le pointeur s'ajoute en C : un type dont les valeurs sont des adresses.

iRemarqueCe que le programme écarte

« Un étudiant est capable d'inférer un type à la lecture d'un fragment de code, cependant toute théorie du typage est hors programme. » On sait donc lire une signature et deviner un type ; on n'étudie ni l'algorithme d'unification, ni les systèmes de types. De même, « la notion de classe et la programmation orientée objet sont hors programme ».

6.2.2 Mutable ou immuable

Définition 6.2La distinction, illustrée en OCaml

Le programme demande cette distinction, et précise qu'elle est « illustrée en langage OCaml ».

	Immuable	Mutable
OCaml	`'a list`, n-uplet, `string`	`'a array`, `'a ref`, champ `mutable`
Effet d'une « modification »	un nouvel objet	l'objet lui-même change
Partage	sans danger	tout détenteur voit le changement


let l1 = [1; 2; 3] in
let l2 = 0 :: l1 in ()      (* l1 est INTACTE : l2 partage sa queue, sans copie *)

let t1 = [| 1; 2; 3 |] in
let t2 = t1 in
t2.(0) <- 99                (* t1.(0) vaut 99 AUSSI : c'est le MÊME tableau *)

AttentionLe partage est un piège, et c'est aussi une force

La ligne let t2 = t1 ne copie rien : elle donne un second nom au même tableau. C'est instantané — et c'est pourquoi Array.copy existe. À l'inverse, 0 :: l1 ne copie rien non plus, et c'est sans danger : personne ne peut modifier l1. L'immuabilité achète le partage gratuit.

6.3 Structure de données abstraite

6.3.1 Un type muni d'opérations

Définition 6.3Structure de données abstraite

Une structure de données abstraite est un type accompagné des opérations qu'on peut lui appliquer, décrites par leur effet et non par leur réalisation. Le programme en fixe le vocabulaire :

constructeur : crée et initialise la structure ;
accesseur : récupère une valeur, sans rien changer ;
transformateur : modifie l'état de la structure.

Exemple 6.4La pile, décrite sans une ligne de mise en œuvre

Opération	Rôle	Effet
`creer()`	constructeur	rend une pile vide
`est_vide(p)`	accesseur	vrai si $p$ n'a aucun élément
`sommet(p)`	accesseur	le dernier élément empilé
`empiler(p, x)`	transformateur	ajoute $x$ au sommet
`depiler(p)`	transformateur	retire et rend le sommet

Rien ici ne dit comment c'est fait. On sait pourtant déjà écrire des algorithmes complets avec ces cinq lignes — vérifier le parenthésage d'une expression, par exemple. C'est cela, l'abstraction : programmer contre un contrat.

6.3.2 Une abstraction, plusieurs mises en œuvre

ImportantLe point central du chapitre

Le programme y revient trois fois : « on distingue la notion de structure de données abstraite de son implémentation », « plusieurs implémentations concrètes sont interchangeables », « on montre l'intérêt d'une structure de données abstraite en terme de modularité ».

Autrement dit : le contrat est un, les réalisations sont plusieurs, et l'algorithme qui utilise le contrat ne doit pas savoir laquelle est en place.

Exemple 6.5Le même contrat, deux réalisations en C


/* pile.h — L'INTERFACE. C'est tout ce que l'utilisateur inclut. */
#ifndef PILE_H
#define PILE_H
#include <stdbool.h>

typedef struct pile_s pile;    /* type OPAQUE : le contenu reste caché */

pile* pile_creer(void);        /* rend une pile vide, ou NULL si échec */
bool  pile_est_vide(const pile* p);
void  pile_empiler(pile* p, int x);
int   pile_depiler(pile* p);   /* précondition : p non vide */
void  pile_detruire(pile* p);
#endif

Le typedef struct pile_s pile; sans définition est le cœur du procédé : l'utilisateur manipule des pile* sans jamais pouvoir en lire les champs. Un fichier pile_tableau.c et un fichier pile_maillons.c peuvent alors offrir le même en-tête, et l'on change de mise en œuvre en recompilant, sans toucher une ligne de l'algorithme.

Exemple 6.6Le même contrat en OCaml : la signature


(* pile.mli — l'interface *)
type 'a t
val creer : unit -> 'a t
val est_vide : 'a t -> bool
val empiler : 'a t -> 'a -> unit
val depiler : 'a t -> 'a          (* lève Empty si la pile est vide *)

Le type 'a t est déclaré sans sa définition : le compilateur interdira toute tentative de le décomposer depuis l'extérieur. La discipline que C obtient par convention, OCaml l'obtient par typage.

6.3.3 Ce que l'abstraction fait gagner

Bonne pratique (Trois bénéfices, mesurables)

On programme avant de réaliser. Le programme le dit : « grâce aux bibliothèques, on peut utiliser des structures de données avant d'avoir programmé leur réalisation concrète ». L'algorithme s'écrit et se teste contre le contrat.
On change de réalisation sans changer l'algorithme. Si les mesures montrent que la pile par maillons alloue trop, on passe au tableau : un fichier change, le reste ne bouge pas.
On raisonne sur des invariants locaux. Les seuls endroits qui peuvent casser l'invariant d'une pile sont les cinq fonctions de son module. Ailleurs, il tient par construction.

AttentionUne abstraction n'est pas gratuite

Passer par des fonctions coûte des appels ; masquer la structure interdit certaines optimisations ; un type opaque en C oblige à l'allocation dynamique, donc à la libération. Le bon réflexe n'est pas « toujours abstraire », c'est « abstraire ce qui a plusieurs réalisations plausibles, ou ce dont l'invariant est fragile ».

6.4 Choisir sa structure : le tableau récapitulatif

ImportantLe coût des opérations décide de la structure

Ce tableau est le fil de tout le second semestre. Chaque ligne sera démontrée dans son chapitre ; on le donne ici comme carte.

Structure	Accès $i$	Recherche	Insertion	Chapitre
Tableau	$O (1)$	$O (n)$	$O (n)$	chap:sequentielles
Tableau trié	$O (1)$	$O (lo g n)$	$O (n)$	chap:sequentielles
Liste chaînée	$O (n)$	$O (n)$	$O (1)$ en tête	chap:sequentielles
Arbre binaire de recherche	---	$O (h)$	$O (h)$	chap:tas
Arbre bicolore	---	$O (lo g n)$	$O (lo g n)$	chap:tas
Tas	---	---	$O (lo g n)$	chap:tas
Table de hachage	---	$O (1)$ en moyenne	$O (1)$ en moyenne	chap:hachage

Les tirets ne sont pas des oublis : un tas ne sait pas chercher un élément quelconque, et un arbre n'a pas d'indice. Une structure ne répond bien qu'aux questions pour lesquelles elle est faite — c'est exactement pourquoi l'algorithme et la structure se conçoivent ensemble.

6.5 Ce qu'il faut retenir

ImportantAbstraction : trois questions avant d'écrire

Quelles opérations vais-je répéter ? Ce sont elles, et non les autres, qui doivent être rapides.
Quel contrat, indépendamment de toute réalisation ? Constructeurs, accesseurs, transformateurs — et l'invariant que la structure maintient.
Quelles réalisations le satisfont, et à quels coûts ? S'il n'y en a qu'une, l'abstraction est peut-être superflue. S'il y en a deux, elle est déjà rentable.

Continuer sur Adloun : animation, QCM, fiches, exercices