Problème — Choisir d'après le profil des opérations — exercice corrigé d'informatique (MP2I/MPI) (chapitre 6)

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

	Tableau	Chaîne
A : $n$ insertions en tête	$Θ (n^{2})$ (décalage)	$Θ (n)$
$100$ lectures par indice	$Θ (1)$ chacune	$Θ (n)$ chacune
Total A	$Θ (n^{2})$	$Θ (n)$
B : $n$ insertions en fin	$Θ (n)$	$Θ (n)$ avec pointeur de queue
$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.

Problème — Choisir d'après le profil des opérations

Énoncé

Corrigé

Exercices semblables