| Votre opinion sur le cours de ce matin : | Votre opinion sur le TD 3 : |
L'objectif de ce TD est de réaliser une structure d'ensemble polymorphe et de l'utiliser pour mettre en œuvre une technique, appelée hash-consing, visant à diminuer l'empreinte mémoire d'une structure de donnée en partageant ce qui est identique. On l'illustre ici avec des arbres binaires.
Le TD devra être réalisé en OCaml.
Le but de cette première partie est de réaliser une structure d'ensemble polymorphe (les éléments sont d'un type quelconque) à l'aide d'une table de hachage.
Dans un fichier hashset.ml, déclarer le type suivant pour
une telle table :
type 'a t = {
buckets: 'a list array;
mutable size: int;
}
Le champ buckets contient un tableau de listes. Sa case
d'indice i recevra les éléments dont la clé de hachage
modulo la taille du tableau vaut i.
On ne cherchera pas à redimensionner ce tableau. Le
champ size contient le nombre d'éléments de l'ensemble.
Écrire une fonction create: int -> 'a t qui construit
une table de hachage vide. L'entier passé en argument est la taille du
tableau.
Doc :
Array.make
Écrire une fonction size: 'a t -> int qui renvoie le
nombre d'éléments, c'est-à-dire le contenu du champ size.
Écrire une fonction
lookup: ('a -> bool) -> 'a list -> 'a option
qui cherche dans une liste le premier élément satisfaisant
un prédicat donné. Si un tel élément x existe, la
fonction renvoie Some x. Sinon, elle
renvoie None.
Déduire de la fonction lookup une fonction
find: ('a -> int) -> ('a -> 'a -> bool) -> 'a t -> 'a -> 'a option
qui cherche un élément donné dans un ensemble.
Si l'élément est présent dans l'ensemble, on renvoie Some
x où x est l'élément contenu
dans l'ensemble (et non pas celui passé en argument, même s'ils sont
égaux pour la fonction d'égalité). Sinon, on
renvoie None.
Les deux premiers arguments sont respectivement la fonction de hachage
et la fonction d'égalité.
On les suppose cohérentes, c'est-à-dire que deux éléments égaux pour
la fonction d'égalité ont la même valeur par la fonction de hachage.
Par ailleurs, on ne suppose pas que la fonction de hachage
renvoie une valeur positive ou nulle. C'est donc au code
de find de s'en assurer avant de calculer le modulo.
Écrire une fonction
add: ('a -> int) -> ('a -> 'a -> bool) -> 'a t -> 'a -> unit
qui ajoute un élément x dans un ensemble,
si un élément égal à x n'est pas déjà présent. Penser à
mettre le champ size à jour le cas échéant.
Les deux premiers arguments sont la fonction de hachage
et la fonction d'égalité, comme pour find.
Tester avec test_hashset.ml.
Déposer le fichier hashset.ml :
On considère ici des arbres binaires contenant des entiers aux nœuds. Un même arbre peut être construit en mémoire de différentes façons, plus ou moins économes. Ainsi, les deux arbres ci-dessous sont structurellement égaux, mais celui de gauche est composé de 9 nœuds en mémoire alors que celui de droite de seulement 5 nœuds.
Le but de cette question est de calculer l'empreinte mémoire d'un
arbre et plus précisément le nombre de nœuds N
distincts qui le représentent en mémoire.
C'est donc, à une constante près, le nombre d'octets
utilisés pour sa représentation.
Dans un fichier tree.ml, déclarer le type suivant pour
les arbres binaires :
type tree = | E | N of tree * int * tree
Écrire une fonction de hachage hash: tree -> int pour ces
arbres. Elle doit être cohérente avec l'égalité structurelle : deux
arbres égaux ont la même valeur par cette fonction.
À part cela, elle est totalement arbitraire.
Néanmoins, on cherchera à traiter les sous-arbres gauche et droit de
façon dissymétrique dans ce calcul.
Écrire une fonction mem_size: tree -> int qui calcule le
nombre de nœuds N physiquement distincts d'un arbre
donné. (Il est inutile de compter les feuilles E, car
leur nombre est un de plus que les nœuds. Par ailleurs, elles sont
représentées en interne comme des entiers.)
Indication : L'idée consiste à remplir une table de hachage avec les
nœuds de l'arbre déjà rencontrés et à se servir de l'égalité
physique == pour les rechercher.
Tester
avec test_mem_size.ml.
Déposer le fichier tree.ml :
Le but de cette question est de diminuer l'empreinte mémoire d'un arbre, en partageant en mémoire ses sous-arbres structurellement égaux. Cette technique, évoquée lors de l'amphi 3, s'appelle le hash-consing.
On continue à travailler dans le fichier tree.ml.
Écrire une fonction share: tree -> tree qui réalise le
partage maximal. Pour un arbre t passé en argument,
cette fonction renvoie un arbre structurellement identique
à t d'empreinte minimale.
Indication : Là encore, l'idée consiste à remplir une table de hachage
avec les sous-arbres déjà rencontrés mais en se servant cette fois de
l'égalité structurelle = pour les rechercher.
Tester
avec test_share.ml.
Déposer le fichier tree.ml :
Les questions suivantes sont optionnelles.
Passer les fonctions de hachage et d'égalité systématiquement aux
fonctions find et add est potentiellement
risqué. En effet, on pourrait ajouter un élément dans l'ensemble avec
certaines fonctions et le rechercher ensuite avec d'autres
(accidentellement, mais le compilateur ne peut pas nous aider à
trouver l'erreur).
Une solution à ce problème consiste à passer les fonctions de hachage
et d'égalité plutôt à la fonction create, au moment de la
construction initiale de l'ensemble, et à les stocker dans la
structure (comme deux autres champs).
Modifier le code de hashset.ml dans ce sens.
Note : il faut adapter test_hashset.ml
et tree.ml en conséquence.
Déposer le fichier hashset.ml :
La fonction share utilise l'égalité structurelle pour
chercher si on a déjà construit un arbre N (l,n,r). On
peut cependant être plus efficace lors de ce test d'égalité. En
effet, si on déjà réalisé le partage des sous-arbres l
et r alors on peut se contenter d'une égalité physique
(==) sur ces sous-arbres.
Écrire une fonction d'égalité qui réalise une égalité structurelle au
plus haut niveau de l'arbre et une égalité physique sur les
sous-arbres. L'utiliser pour obtenir une fonction share
plus efficace.
Déposer le fichier tree.ml :
Une solution vous est proposée.