Pourquoi l'anti-jointure emploie-t-elle un set

Exercice supplémentaire · niveau 2 · NSI (première), chapitre 6 — Traiter des données en tables · Mesurer le coût plutôt que l'annoncer

Énoncé

Pourquoi l'anti-jointure emploie-t-elle un set ? Mesurer le coût du test d'appartenance dans une liste, sur des tailles doublantes, et conclure.

Corrigé

La mesure. On compte les comparaisons pour $50$ tests d'appartenance dans une liste de $n$ éléments, dans le pire cas — la valeur cherchée est toujours la dernière.

$n$	comparaisons	rapport
$200$	$10000$	---
$400$	$20000$	$2, 0$
$800$	$40000$	$2, 0$
$1600$	$80000$	$2, 0$

Le coût d'un test est linéaire en $n$ : c'est le parcours séquentiel du chapitre 7. Avec un set ou un dictionnaire, il ne dépend pas de $n$ (chapitre 5).

La conséquence sur l'anti-jointure. Avec une liste, chacun des $n_{1}$ tests coûte $n_{2}$ comparaisons : le total est $n_{1} \times n_{2}$ , quadratique — exactement ce que la jointure indexée cherchait à éviter. Avec un ensemble, le total est $n_{1} + n_{2}$ . Un seul caractère de différence dans le code — accolades au lieu de crochets — change la loi de coût.

Ce que la mesure ne montre pas. Elle mesure le pire cas, valeur en dernière position. Si les valeurs cherchées sont souvent en tête, la liste s'en tire bien mieux en moyenne — mais la loi de croissance, elle, reste linéaire.

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.