Probleme – Un ensemble d'entiers, trois réalisations, un critère

Exercice · niveau 3 (difficile) · informatique (MP2I/MPI), chapitre 6 — Types et structures de données abstraites

Énoncé

On veut le contrat : vide, ajouter, appartient, cardinal, sur des entiers de $[0, u [$ .

Écrire la réalisation par liste non triée, par liste triée, et par tableau de booléens.
Donner la complexité de chaque opération dans chaque cas.
Mesurer, et expliquer l'écart.
Sur quel critère choisit-on ?

Corrigé

1. Les trois réalisations.


(* A. liste NON triee, sans doublon *)
let a_vide = []
let a_appartient x s = List.mem x s
let a_ajouter x s = if List.mem x s then s else x :: s

(* B. liste TRIEE sans doublon *)
let rec b_appartient x = function
  | [] -> false        | y :: _ when x = y -> true
  | y :: _ when x < y -> false      (* triee : inutile d'aller plus loin *)
  | _ :: r -> b_appartient x r
let rec b_ajouter x = function
  | [] -> [x]
  | y :: r when x < y -> x :: y :: r
  | y :: r when x = y -> y :: r
  | y :: r -> y :: b_ajouter x r

(* C. vecteur caracteristique : une case par valeur possible *)
let c_vide () = Array.make u false
let c_appartient x s = s.(x)
let c_ajouter x s = s.(x) <- true

2. Les coûts, pour un ensemble de $n$ éléments pris dans $[0, u [$ :

	`appartient`	`ajouter`	`cardinal`	Mémoire
A. liste non triée	$O (n)$	$O (n)$	$O (n)$	$Θ (n)$
B. liste triée	$O (n)$	$O (n)$	$O (n)$	$Θ (n)$
C. tableau de booléens	$Θ (1)$	$Θ (1)$	$Θ (u)$	$Θ (u)$

Noter que B ne gagne aucun ordre sur A : la recherche s'arrête plus tôt en moyenne, mais elle parcourt toujours. C'est l'objet du huitième exercice de ce chapitre.

3. La mesure, pour $n$ insertions suivies de $n$ recherches, avec $u = 1 0^{5}$ :


n =  1000 : A 0,025 s    B 0,027 s    C 0,004 s
n =  5000 : A 0,581 s    B 0,653 s    C 0,004 s
n = 20000 : A 9,347 s    B 11,092 s   C 0,007 s

Quand $n$ est multiplié par $4$ , le temps de A et B est multiplié par $16$ : coût quadratique, conforme à $n$ opérations en $O (n)$ . Celui de C ne bouge pas : $2 n$ opérations en $Θ (1)$ , et le temps est dominé par l'allocation des $1 0^{5}$ cases, qui ne dépend pas de $n$ .

B est même légèrement plus lente que A — $11, 1$ contre $9, 3$ secondes. L'insertion triée doit reconstruire le préfixe de la liste jusqu'au point d'insertion, alors que l'insertion en tête ne fabrique qu'un maillon. Le tri se paye à l'écriture ce qu'il rapporte à la lecture, et sur une chaîne il ne rapporte qu'un facteur constant.

4. Le critère. Il tient au rapport $u / n$ :

Si $u$ est petit et connu d'avance — des jours de l'année, des codes ASCII, des sommets d'un graphe —, le vecteur caractéristique gagne toujours, et il gagne de plusieurs ordres. C'est la structure la plus sous-employée du programme.
Si $u$ est immense ou inconnu — des chaînes de caractères, des entiers quelconques —, le vecteur est impossible et l'on veut une table de hachage : $O (1)$ en moyenne pour un espace $Θ (n)$ , chapitre chap:hachage.
La liste triée ne se justifie que si l'on a besoin de parcourir les éléments dans l'ordre, ce que ni A ni C ne donnent gratuitement.

Et c'est la démonstration de la thèse du chapitre : le contrat n'a pas changé, l'algorithme utilisateur n'a pas changé, et le temps a été divisé par mille. « 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. »

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.