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.
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.
Fig 3: La numérotation des cellules.
Ajoutez à la classeSite
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)/2 +x/R;
}
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.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.
HashMap<Integer,SiteList> grid;
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. 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 commandejava ShowNeighbors tests/T01.txt
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é. 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.