informatique (tronc commun des prépas scientifiques) · Chapitre 17 · Exercice de TD
L'ensemble, dictionnaire sans valeurs
Les dictionnaires dévoilés : le hachage · niveau 3 (difficile)
Énoncé
(a) Implémenter un ensemble de clés hachables en proposant les fonctions ens_creer(m), ens_ajouter(ensemble, cle) et ens_contient(ensemble, cle). Écrire à l'aide de cet ensemble la recherche du premier doublon d'une liste premiere_repetition(t). (b) Comparer et chronométrer l'exécution de cette fonction avec une implémentation basée sur une liste de déjà-vus pour éléments. (c) Discuter du lien structurel entre dictionnaire et ensemble.
Corrigé de la question 1
(a)
def ens_creer(m: int) -> list:
return [[] for _ in range(m)]
def ens_ajouter(ensemble: list, cle) -> None:
alv = ensemble[hash(cle) % len(ensemble)]
if cle not in alv:
alv.append(cle)
def ens_contient(ensemble: list, cle) -> bool:
alv = ensemble[hash(cle) % len(ensemble)]
return cle in alv
def premiere_repetition(t: list):
# On crée un ensemble avec une taille suffisante pour éviter trop de collisions
vus = ens_creer(2 * len(t))
for x in t:
if ens_contient(vus, x):
return x
ens_ajouter(vus, x)
return NoneQuestion 2 : comment l'IA t'aide
(b) Comparer et chronométrer l'exécution de cette fonction avec une implémentation basée sur une liste de déjà-vus pour éléments.
Élève
J'ai chronométré sur une liste aléatoire de entiers : les deux versions trouvent vite un doublon et les temps se ressemblent. La table de hachage n'apporterait donc rien ?
IA
Ta mesure dépend de l'entrée : dans une liste aléatoire, un doublon apparaît souvent très tôt, et les deux fonctions s'arrêtent avant d'avoir fait l'essentiel du travail. Quelle entrée les force à aller jusqu'au bout ?
Élève
Une liste sans aucun doublon, par exemple les entiers de à . Là, la version à liste confronte chaque nouvel élément à tous les déjà-vus.
IA
Exactement. Combien de comparaisons la version à liste fait-elle alors au total ? Et pour la version à ensemble, avec alvéoles, quelle est la longueur moyenne d'une alvéole consultée, et quel rapport de temps attends-tu ?
L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.
Continue cet exercice avec l'IA
Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.
Continuer avec l'IA — gratuit, sans inscriptionGratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.