info@mp2i-pv
Il s’agit dans ce TP de constater expérimentalement l’efficacité des tables de hachage pour stocker des ensembles (d’entiers pour simplifier).
Nous nous intéressons à la gestion des collisions par chaînage et nous voulons déterminer expérimentalement la bonne taille de table de hachage en fonction du nombre de données à stocker.
Les fichiers d’en-tête qui spécifient les types et les fonctions à implémenter: hachage.h / liste.h.
Tout est dans le titre… la liste des fonctions se trouvent dans le fichier d’en-tête.
Le champ hacher un peu bizarre qu’on voit dans le fichier d’en-tête
et le paramètre assez similaire de la fonction init
permettent de manipuler des fonctions comme des valeurs (comme dans le
cas des tableaux, le nom d’une fonction est converti implicitement en
son adresse). Il s’agit ici de conserver l’adresse de la fonction de
hachage dans la table de hachage.
Par exemple on pourrait écrire:
int zero(int n, int p){ // les paramètres sont là pour le type de la fonction
return 0;
} // très peu intéressant comme fonction de hachage
int main(void){
hachage h;
h.hacher = zero;
}
(Les types comme celui du champ hacher sont hors programme et je ne
vous demande pas de savoir les manipuler, mais là il s’agit juste
d’utiliser une fonction comme paramètre d’une autre.)
Varier les fonctions de hachage:
random quand on fait un srandom sur
la valeur à stocker,a et partie entière inférieure de
n*(k*a % 1) où n est la taille de la table et k la clef considérée.Je vous fournis les fichiers temps.h / temps.c qui permettent de mesurer le temps d’exécution d’une partie d’un programme.
Il s’agit de faire des statistiques sur les temps d’insertion, de consultation et de suppression d’élément dans votre table de hachage.
Pour les tracés, on utilisera gnuplot (essayez de le lancer en ligne
de commande dans un terminal, si ce n’est pas installé, appelez-moi).
Une fois gnuplot lancé, vous pouvez utiliser la commande
gnuplot> plot "donnees" using 2:3 with lines
pour tracer la courbe représentant les données de la 3e colonne en
fonction de celles de la deuxième colonne, du fichier donnees.
Voici un extrait d’un de mes fichiers de données comme exemple :
# taille nb insertion temps insertions nb suppression suppressions
100 0 -12.023751 0 -12.716898
100 100 -10.289150 50 -11.330604
100 200 -9.903488 100 -10.724468
100 300 -9.396670 150 -10.260162
100 400 -9.097012 200 -9.903488
100 500 -8.633727 250 -9.596003
100 600 -8.633727 300 -9.361163
100 700 -8.458924 350 -9.133379
100 800 -8.115067 400 -8.873868
On suppose qu’on a une table de hachage de N alvéoles. On veut
connaître le temps mis pour M insertions prises au hasard, le temps
de consultation pour M/2 consultations au hasard et le temps de
suppression pour M/2 suppressions au hasard.
Faites des graphiques où N est fixé et M varie, et des graphiques
où N/M est fixé et N et M varient.
Faites les mêmes expériences en gérant les collisions par sondage.
Un joli sujet de compression.