SkayaWiki

L2.2-01

JeromePetazzoni :: DerniersChangements :: DerniersCommentaires? :: ParametresUtilisateur :: http://www.enix.org/ :: Vous êtes ec2-3-239-15-34.compute-1.amazonaws.com

Tables de hachage & généricité


Le but de ce TD est d'écrire des fonctions génériques (c'est-à-dire adaptées à tous les types de données, sans qu'il soit nécessaire de les réécrire ou même de les modifier) pour gérer des listes chaînées, puis des tables de hachage.

Listes chaînées


Préliminaires : un peu de récursivité


Nous allons commencer par écrire (encore!) un mécanisme de gestion de listes chaînées. Le type des éléments contenus dans la liste chaînée sera void* - cela permettra de faire facilement des listes de n'importe quoi. Nous allons
prendre comme base une structure définie comme suit :

struct liste_s {
void* tete;
struct liste_s* queue;
};

Le void* tete est la donnée contenue dans la tête de liste (son premier élément, autrement dit!). Quant à queue, il s'agit de la suite de la liste. Si la liste est vide, ces deux pointeurs sont égaux à NULL. Si la liste est composée d'un seul élément, sa tête est ce premier élément ; quant à la queue, c'est un pointeur vers une liste vide (c'est-à-dire avec ses deux pointeurs tête et queue égaux à NULL). Autrement dit : on ne doit jamais avoir queue==NULL, sauf si - et seulement si - tete == NULL.

On va écrire les fonctions de gestion de listes chaînées classiques, MAIS avec une contrainte particulière : ne pas utiliser de boucle for ou while, ni de compteur, pour parcourir les listes. À la place, il faudra utiliser la récursivité. Par exemple, pour calculer la longueur d'une liste, au lieu de créer un compteur et de parcourir la liste, on pourra écrire une fonction liste_longueur qui renverra 0 si la liste est vide, et 1+liste_longueur(queue de liste) dans les autres cas. Écrire en suivant ce principe les fonctions de gestion de listes chaînées suivantes :

struct liste_s* liste_creation(); /* crée une liste vide */
void liste_destruction(struct liste_s*
* liste); /* libère la mémoire de la liste */
void liste_ajout_en_tete(struct liste_s* liste, void* element);
void liste_ajout_en_queue(struct liste_s* liste, void* element);
void *liste_retire_tete(struct liste_s *
*liste);

Notez que jusqu'ici, quel que soit le type réel des éléments de la liste, le code ne change pas d'un iota - le code est donc parfaitement générique. Ceci va bientôt changer ...

Récupérez le fichier liste.c, completer les fonctions et ajouter des commentaires au début de
chaque fonction en suivant les mêmes régles d'écriture que les commentaires déjà présents. Il s'agit de balises spéciales, qui seront utilisées par le programme doxygen au paragraphe suivant.

Récupérez le fichier doxy, et mettez le dans le même répertoire
que liste.c. Exécutez la commande doxygen doxy, et consultez le répertoire html avec votre
navigateur favori.

Va-t-on perdre la généricité ?


À partir de maintenant, on suppose qu'on dispose des deux fonctions suivantes (vous n'avez PAS à les écrire pour l'instant) :

int compare_deux_elements(void* e1, void* e2); /* renvoie 0 s'ils sont égaux, autre chose sinon */
void affiche_element(void* element); /* affiche sur la sortie standard l'élément correspondant, sur une ligne (avec un \n au bout) */

On vous demande (en faisant comme si ces fonctions existaient) d'écrire les fonctions suivantes :

void liste_affiche(struct liste_s* liste); /* affiche les éléments de la liste, un par ligne */
void* liste_recherche_element(struct liste_s* liste, void* element); /* recherche l'élément dans la liste ; si il est trouvé, le renvoie ; sinon, renvoie
NULL */
void liste_efface_element(struct liste_s*
* liste, void* element); /* cherche l'élément dans la liste, et le supprime de la liste à chaque fois qu'il est trouvé */
void liste_ajoute_element(struct liste_s*
* liste, void* element); /* ajoute l'élément uniquement s'il N'est PAS déjà dans la liste */

IMPORTANT : à chaque fois que vous devrez comparer des éléments, n'utilisez pas simplement == mais plutôt la fonction compare_deux_elements.

Application


Nous allons supposer que les données contenues dans la liste chaînée sont des mots - c'est-à-dire des char*. Écrire les fonctions compare_deux_elements et affiche_element correspondantes, puis vérifier le bon fonctionnement de l'ensemble (ajoutez une dizaine de mots avec la fonction liste_ajoute_element, dont certains en double, et vérifiez que lorsque vous appelez liste_affiche, il n'ont été insérés qu'une seule fois et qu'il n'y a pas de doublons).

Si ça marche, bravo, vous pouvez considérer que vous avez vraiment compris les listes chaînées. Sinon, malheureusement, il va falloir les réviser encore un peu ...

Retour de la généricité


Comme vous l'avez certainement remarqué, l'introduction des deux fontions compare_deux_elements et affiche_element nous a fait perdre le caractère "universel" de nos fonctions. Nous allons donc introduire une nouvelle structure pour ranger ces fonctions. L'idée est la suivante : pour chaque "type" (nous dirons classe) d'éléments manipulés, nous aurons une structure différente, contenant des fonctions différentes.

struct classe_s {
int(*compare)(void* e1, void* e2);
void(*affiche)(void* e1);
};

Pour démystifier un peu cette écriture, voici un petit exemple :

struct point_s {
int x, y;
};
int compare_point(void* e1, void* e2) {
struct point_s *p1 = e1, *p2 = e2;
return (p1->x=
=p2->x && p1->y==p2->y);
}
void affiche_point(void* element) {
struct point_s *point = element;
printf("x=%d, y=%d\n", point->x, point->y);
}
struct classe_s classe_point = { compare_point, affiche_point };

Ensuite, nous allons modifier la structure de liste pour y inclure cette notion de "type" :

struct liste_s {
void* tete;
struct liste_s* queue;
struct classe_s* classe;
};

Et enfin, modifier quelques fonctions - tout d'abord, la fonction de création devra maintenant être :

struct liste_s* liste_creation(struct classe_s* classe);

D'autre part, les fonctions qui utilisent les fonction de comparaison et d'affichage doivent être modifiées afin d'utiliser les fonctions contenues dans la structure classe. Adapter l'exemple sur les noms pour vérifier que tous ces nouveaux concepts sont correctement compris et implémentés.

Application : dictionnaire


On demande d'écrire un programme dico qui prend au moins deux arguments (au moyen d'argv) : un fichier contenant une liste de mots (par exemple /usr/share/dict/french), et un ou plusieurs mots. Le programme doit charger complètement le dictionnaire en mémoire, puis indiquer pour chaque mot s'il existe ou pas dans le dictionnaire. Par exemple :

dico /usr/share/dict/french abandon kaouète zouave zapoyoko

Pour charger le dictionnaire, on pourra utiliser tout simplement fopen et fscanf :

char mot[100];
FILE* dict = fopen("/usr/share/dict/french","r");
while (EOF!=fscanf(dict, "%s", mot)) { liste_ajoute_element(liste, strdup(mot)); }
fclose(dict);

Comparer ensuite avec time (exemple : time dico /usr/blabla mots...) le temps nécessaire pour chercher un mot, selon qu'il est au début, à la fin, au milieu... du dictionnaire.

Tables de hachage


Nous allons proposer une solution plus rapide que les listes chaînées. Le principe va être le suivant : au lieu de mettre tous les éléments dans une seule liste chaînée, nous allons les répartir en plusieurs listes. Par exemple, si nos éléments étaient des nombres, nous pourrions avoir une liste pour les nombres pairs, et une autre pour les nombres impairs. La longueur moyenne des listes serait divisée par deux, et la recherche irait donc en moyenne deux fois plus vite.

Ici, nos éléments sont de type arbitraire, et le nombre de listes aussi ! Nous allons considérer que le nombre de listes (qu'on appellera M par la suite) est fixé lors de la création de la structure de données - qu'on appellera à partir de maintenant table de hachage. Si à un moment donné, on souhaite changer ce nombre, il faudra créer une nouvelle table de hachage, y copier les données de l'ancienne table, puis détruire cette dernière.

Fonction de hachage


La fonction de hachage est précisément la fonction qui permet de savoir "dans quelle liste dois-je mettre cet élément?". Cette fonction doit prendre pour argument un élément, et renvoyer un nombre entre 0 et M-1 (un numéro de liste). Comme il peut y avoir un nombre arbitraire de listes, et qu'il serait dommage de devoir changer de fonction de hachage à chaque fois, nous allons considérer que la fonction de hachage doit renvoyer un nombre entre 0 et N (avec N suffisamment grand), et nous utiliserons ensuite l'opérateur modulo pour ramener cet entier entre 0 et M.

Il est assez difficile d'écrire une bonne fonction de hachage ; aussi, voici une fonction "cadeau" pour les chaînes de caractères :

unsigned int h(unsigned char *chaine) {
unsigned int c, hash = 5381;
while (c = *chaine++) hash = ((hash << 5) + hash) + c;
return hash;
}

Nous allons aussi modifier la structure de classe afin d'y introduire cette fonction :

struct classe_s {
int(*compare)(void* e1, void* e2);
void(*affiche)(void* element);
unsigned int(*hache)(void* element);
};

La structure table de hachage proposée est la suivante :

struct table_s {
struct classe_s* classe;
int m; /* nombre de listes dans le tableau suivant */
struct liste_s*
* table; /* tableau de listes chaînées */
};

Au travail!


Il va falloir écrire les fonctions suivantes :

struct table_s* table_creation(struct classe_s* classe, int m_initial); /* crée table de hachage vide */
void table_destruction(struct table_s*
* table); /* libère la mémoire de la table */
void table_affiche(struct table_s* table); /* affiche les éléments de la table, un par ligne */
void* table_recherche_element(struct table_s* table, void* element); /* recherche l'élément dans la table ; si il est trouvé, renvoie l'élément contenu dans la table ; sinon, renvoie
NULL */
void table_efface_element(struct table_s* table, void* element); /* cherche l'élément dans la table, et le supprime de la table à chaque fois qu'il est trouvé */
void table_ajoute_element(struct table_s* table, void* element); /* ajoute l'élément uniquement s'il N'est PAS déjà dans la table */

Bien sûr, il est fortement conseillé de réutiliser les fonctions de listes écrites plus haut ! En fait, vous pouvez même les utiliser telles quelles, normalement.

Comparaison avec les listes chaînées


Reprenez le programme dico, mais avec une table de hachage (vous l'appellerez dicoh). Essayez avec différentes tailles de table de hachage, comparez les temps d'exécution.


Bonus


La liste générique que vous venez d'implémenter présente certains inconvénients: donner les et proposer des solutions. Ré-implémenter
des listes génériques sur la base de ces solutions.

Un concept bien pratique est la notion d'iterateur. Un iterateur est une structure associée à un conteneur (la liste par exemple) et qui représente une position dans ce conteneur. Une fonction iterateur_suivant permet de faire avancer l'iterateur sur l'élément suivant et une fonction iterateur_element permet d'obtenir l'élément courrant.
Ecrire une structure permettant de mettre en oeuvre ces iterateurs ainsi que les fonctions liste_debut permettant d'obtenir
un itérateur sur le premier élément d'une liste et table_debut permettant d'obtenir un itérateur sur le premier élément d'une table.

Compte-rendu


Vous devrez envoyer avant le TD suivant un mail à systeme at enix point org, avec comme sujet (exactement!) [L2.2-01 votrelogin] (avec les crochets), et contenant une archive tar avec les sources de vos programmes. Indiquez en particulier comment compiler dico et dicoh. Vos programmes seront testés, donc il faut qu'ils marchent :-)


TD suivant
Il n'y a pas de commentaire sur cette page. [Afficher commentaires/formulaire]