Problème — Un ensemble d'entiers, trois réalisations, un critère — exercice corrigé d'informatique (MP2I/MPI) (chapitre 6)

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. »

Problème — Un ensemble d'entiers, trois réalisations, un critère

Énoncé

Corrigé

Exercices semblables