TD 4: Tables de hachage
par Christoph Dürr

 Login :  Mot de passe :

1. Présentation

Aujourd'hui, nous allons étudier les tables de hachage, plus précisément les tables d'association. Pour cela nous considérons une application des réseaux mobiles. Soient N personnes réparties un peu n'importe comment sur un terrain, et équipées d'un ordinateur portable avec wifi. Deux personnes sont voisines, c'est-à-dire peuvent communiquer si et seulement si leur distance est inférieure ou égale à une distance R, qui représente la portée du wifi d'un ordinateur. Le but est maintenant de trouver qui est voisin avec qui. Formellement on reçoit un tableau de N sites de coordonnées non-négatives, un rayon R, et on doit fournir la liste de toutes les paires de sites voisins.

Fig 1: A et B sont voisins car leur distance est inférieure ou égale à R, alors que C n'est pas voisin de A.

Il y a un algorithme simple qui consiste à tester toutes les O(N2) paires. Mais il y a mieux. On découpe le terrain en une grille dont chaque cellule est de dimension R*R. Alors deux sites voisins sont soit dans la même cellule soit dans des cellules adjacentes. Maintenant on crée une table qui associe à chaque cellule la liste des sites qu'elle contient. Finalement on teste pour chaque site S la distance avec tous les sites contenus dans la cellule contenant S et dans les huit cellules adjacentes. 

Fig 2: La grille composée de cellules R*R. Les neuf cellules dans lesquelles il faut chercher les voisins d'un site donné.

La complexité de cet algorithme est aussi en O(N2) dans le pire des cas, ce qui pourrait arriver si tous les sites sont localisés dans la même cellule. Mais avec un peu de chance ils sont distribués de telle manière que le nombre de points par cellule est borné par une constante. Dans ce cas la complexité de l'algorithme est en O(N), ce qui est une amélioration considérable : certaines tailles d'instances peuvent être traitées dans l'ordre d'une seconde, là où l'algorithme en O(N2) mettrait plus d'une semaine. Si cela vous intéresse, calculez (mais après le TD) la complexité en moyenne de cet algorithme si N sites sont uniformément aléatoirement distribués sur cN cellules, pour une constante c.

2. Les Sites

Commencez par écrire une classe Site qui contient des coordonnées entières x,y et un rayon R. Ce rayon sera le même pour toutes les instances de la classe, donc appliquez le slogan du cours pour le déclarer correctement. Le constructeur prendra deux entiers x,y en paramètres. Ajoutez une méthode double distanceTo(Site t) qui retourne la distance entre le site et un autre site donné en utilisant la méthode hypot.

Nous avons besoin d'identifier les cellules par un entier unique. Pour cela nous adoptons la convention suivante.

Fig 3: La numérotation des cellules.

Ajoutez à la classe Site la méthode suivante.

    
/* retourne un identifiant de la cellule contenant ce Site dans
       la grille dont les cellules ont la dimension R*R
    */
    int cell() {
        int d = x/R + y/R;
        return d*(d+1)/+x/R;
    }

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

3. Le programme principal

Pour vous épargner les difficultés des entrées/sorties en Java on vous fourni une classe ShowNeighbors. Elle comporte un programme principal, qui ouvre un fichier donné, lit les sites qui y sont décrits, puis appelle la méthode  static void findCloseSites(Site [] sites, PairReciever p) de la classe CloseSites, que vous allez maintenant écrire. La seule chose qui doit vous intéresser sur la classe ShowNeighbors c'est qu'elle implémente l'interface suivante.

interface PairReciever {
    void addPair(Site a, Site b);
}

Pour chaque paire de sites voisins a,b votre méthode findCloseSites va appeler p.addPair(a,b), pour permettre l'affichage de vos résultats. L'appel de findCloseSites veut dire : bonjour, voici un tableau de sites, et une classe p qui sait traiter des voisins. S'il te plaît, trouves-moi toutes les paires de sites voisins et passe les à p. Cette manière de communiquer entre classes est typique des callbacks utilisés dans les interfaces graphiques, ou de la programmation fonctionnelle.

4. Stocker les sites dans la grille 

Nous allons écrire dans la question suivante la classe CloseSites. Pour commencer il nous faut une structure de données qui associe à chaque cellule la liste des sites qu'elle contient. La classe HashMap nous convient parfaitement. Cette classe est générique, c'est-à-dire qu'on doit indiquer entre chevrons de quel type sont les clés et de quel type sont les valeurs. Les clés seront les identifiants des cellules, donc des entiers. Mais comme HashMap a besoin d'une classe pour le type de clés, nous allons utiliser la classe Integer au lieu du type simple int. Ceci ne concerne que la déclaration, lors de l'utilisation de la classe on peut utiliser nos clés de type int, la conversion en Integer se fait automatiquement.

Une cellule peut contenir plusieurs sites, les valeurs seront donc de type liste de sites. Écrivez une classe SiteList en vous inspirant du poly (voir sec1.1 PointList).

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

5. Trouver les voisins

Le type de notre variable grille (grid en anglais) sera alors

    
HashMap<Integer,SiteList> grid;
et sera une variable locale à la méthode findCloseSites que vous allez écrire maintenant. Désormais nous sommes prêts pour écrire la partie principale de notre algorithme. Ecrivez une classe CloseSites avec une méthode static void findCloseSites(Site [] sites, PairReciever p). Dans un premier temps on va ajouter les sites donnés à notre table d'association grid. Servez vous de cette manière d'itérer sur un tableau que vous avez vu ce matin dans le cours.

Puis dans un deuxième temps, pour chaque site S on cherche dans les neufs cellules environnantes (celle de S inclus) des voisins. Astuce : pour cela créez des sites temporaires aux coordonnées (s.x-R, s.y-R), (s.x, s.y-R), (s.x, s.y+R), (s.x-R, s.y), etc. et parcourez la liste associée à leurs cellules. Voici les affichages que vous devriez obtenir pour les fichiers tests fournis. Votre programme s'éxécute avec la commande

java ShowNeighbors tests/T01.txt

 

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

6. Trouver les composantes connexes (optionnel)

Une composante connexe est un ensemble maximal de sites, tel que pour chaque paire de sites S,T il existe une séquence de sites S=S1,S2,...,Sk=T et pour 1<=i<k les sites Si,Si+1 sont voisins. Chaque site se trouve dans exactement une composante. Pour cela nous allons augmenter la classe Site d'un champs Site supervisor (supérieur hiérarchique en anglais). Dans chaque composante il y aura exactement un site appelé chef. Si pour un site S, S.supervisor est null alors S est le chef de sa composante. Sinon récursivement le chef de S est le chef de S.supervisor. Ajoutez une méthode Site boss() qui retourne le chef de la composante d'un site donné.

Initialement chaque site est dans une composante à lui tout seul, donc supervisor est null pour tout le monde. Puis à chaque nouvelle paire de voisin trouvée S,T il faut fusioner les composantes de S et de T. Ceci se fait tout simplement en modiant le chef de S : son supérieur hiérarchique est mainteant le chef de T. On aurait aussi pu inverser les rôles de S et T. En fait il faut faire ce choix intelligement pour que la fonction chef prenne toujours un temps O(log N). Il nous faut donc ajouter un champs int rank à la classe Site. Le rang d'un chef est défini comme étant le nombre maximal de supérieurs hiérarchiques par lesquels il faut passer pour atteindre le chef. Ce champs sera considéré seulement pour les chefs, et ignoré pour les autres sites. Maintenant il suffit de fusioner la composante dont le chef a le plus petit rang dans l'autre composante. Dans le cas où leurs rangs sont pareils, il faut incrémenter le rang de celui qui est resté chef après la fusion. Ajoutez une méthode static void fusion(Site S, Site T) qui réalise cette fusion et maintient le champs rank. Pensez à poser rank=1 dans le constructeur de la classe Site. Appelez fusion pour chaque nouvelle paire de voisin trouvée.

Testez votre code avec cette deuxième version de la classe ShowNeighbors fournie qui affiche pour chaque composante les sites dans une couleur propre. Vous devriez avoir le résultat suivant.