Des arbres en partage
par Jean-Christophe Filliâtre

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.

Tables de hachage

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.

Tester avec test_hashset.ml.

Déposer le fichier hashset.ml :

Empreinte mémoire d'un arbre

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

Tester avec test_mem_size.ml.

Déposer le fichier tree.ml :

Partage maximal

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.

Tester avec test_share.ml.

Déposer le fichier tree.ml :

BONUS : questions subsidiaires

Les questions suivantes sont optionnelles.

Passage des fonctions de hachage et d'égalité

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).

Déposer le fichier hashset.ml :

Un partage plus efficace

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.

Déposer le fichier tree.ml :

Notes


Une solution vous est proposée.