Probleme – Choisir d'après le profil des opérations

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

Énoncé

Deux applications manipulent $50000$ entiers.

A insère $50000$ fois en tête, puis lit $100$ fois par indice.
B insère $50000$ fois en fin, puis lit $50000$ fois par indice.

Prévoir, pour chaque application, le coût total avec un tableau puis avec une chaîne de maillons.
Mesurer.
Quelle règle générale en tirer, et quel piège la règle cache-t-elle ?

Corrigé

1. La prévision. On note $n = 50000$ .

	Tableau	Chaîne
A : $n$ insertions en tête	$Θ (n^{2})$ (décalage)	$Θ (n)$
\phantom{A :} $100$ lectures par indice	$Θ (1)$ chacune	$Θ (n)$ chacune
Total A	$Θ (n^{2})$	$Θ (n)$
B : $n$ insertions en fin	$Θ (n)$	$Θ (n)$ avec pointeur de queue
\phantom{B :} $n$ lectures par indice	$Θ (1)$ chacune	$Θ (n)$ chacune
Total B	$Θ (n)$	$Θ (n^{2})$

Les deux profils sont exactement inverses : chacun est quadratique pour une structure et linéaire pour l'autre.

2. La mesure, en C, sans optimisation :


A : tableau 1,063 s     chaine  0,003 s        rapport : 350
B : tableau 0,0001 s    chaine  1,451 s        rapport : 14 500

La prévision est confirmée dans les deux sens. Et les rapports mesurés collent au compte d'opérations : pour A, le tableau fait $n^{2} /2 \approx 1, 25 \times 1 0^{9}$ déplacements contre $n + 100 \times n /2 \approx 2, 6 \times 1 0^{6}$ pour la chaîne, soit un rapport prédit de $490$ pour $350$ mesurés ; pour B, la chaîne fait $n \times n /2 \approx 1, 25 \times 1 0^{9}$ pas de parcours contre $2 n = 1 0^{5}$ accès pour le tableau, soit $12500$ prédits pour $14500$ mesurés.

3. La règle, et son piège. La règle est celle du chapitre : si l'on accède par indice, tableau ; si l'on insère et supprime en tête, maillons.

Le piège qu'elle cache est qu'on ne l'applique pas au bon niveau. Ce qui décide n'est pas l'opération la plus visible dans le code, c'est celle qui est répétée le plus souvent — et les deux ne coïncident pas. Dans l'application A, la lecture par indice apparaît dans le programme au même titre que l'insertion ; elle n'a lieu que $100$ fois contre $50000$ , et c'est cela qui tranche. Une structure ne se choisit pas sur la liste des opérations, mais sur leur profil, c'est-à-dire leurs nombres relatifs.

Deux corollaires pratiques.

Il faut compter avant de choisir, et le comptage se fait sur le cas d'usage réel, pas sur l'intention. Si l'on ne sait pas compter, on mesure — c'est ce que l'on vient de faire.
Le profil peut changer en cours de vie. Une structure remplie une fois puis lue mille fois n'a pas le même profil pendant les deux phases : on construit alors avec une chaîne, et l'on convertit en tableau avant la phase de lecture. Le coût de la conversion, $Θ (n)$ , est amorti dès la première dizaine de lectures.

Et l'on remarquera que rien de tout cela n'a demandé de changer l'algorithme : c'est le point de départ du chapitre, et sa conclusion.

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.