Nous allons effectuer des statistiques sur les prénoms des
élèves du cours INF421. Pour cela, vous disposez du fichier ListeEleve.java qui contient
une liste toutInf421
avec les noms et les prénoms des élèves du cours.
Il suffit de
copier le fichier dans votre répertoire de travail pour pouvoir
accéder à ListeEleve.toutInf421 depuis
votre programme.
Nous allons associer à chaque prénom le nombre d'élèves le possédant.
Écrire pour cela une classe Assoc permettant de
construire une liste d'associations prénom/nombre. En termes
techniques, le prénom sert de clé et le nombre de
valeur. Il s'agit donc de construire une liste dans laquelle
chaque cellule contient une clé et une valeur.
Écrire les méthodes suivantes pour ajouter et consulter des associations dans une liste :
static Assoc add (Assoc l, String key, int value) qui
permet d'ajouter une association clé/valeur à une liste d'associations et
renvoie la liste résultante (on l'utilisera par exemple par
l = add (l, "John", 18)).
static int get (Assoc l, String key) qui permet de récupérer
la valeur associée à une clé. (Notons que s.equals (t)
permet de tester si deux chaînes de caractères s
et t sont égales.)
Si la liste ne contient aucune
association avec la clé donnée, la méthode pourra provoquer une erreur
au moyen de throw new Error ().
static boolean containsKey (Assoc l, String key)
qui permet de tester si la liste contient une association de clé donnée.
static void print (Assoc l) qui affiche toutes les
associations de la liste.
On pourra se contenter d'une implémentation
très simple de liste d'associations dans laquelle plusieurs
associations avec la même clé peuvent apparaître. Cependant,
lors d'un get, c'est la dernière valeur
associée à la clé qui doit être renvoyée.
Construire la liste d'associations correspondant au compte des
prénoms dans la liste
ListeEleve.toutInf421, et trouver ainsi les prénoms les plus
répandus en INF421.
Pour y voir plus clair, vous pouvez utiliser la
commande sort qui permet de trier les lignes
d'un fichier comme expliqué ci-dessous. Imaginons que
l'exécution java Assoc affiche une sortie du
type :
Julien 2 Albert 3 Moi 1 ...
Vous pouvez rediriger la sortie de votre programme vers un fichier par la commande java Assoc > output.txt. (En unix, la syntaxe com > fic indique de rediriger la sortie de la commande com dans le fichier fic au lieu de l'afficher dans la fenêtre terminal.)
La commande sort --numeric-sort --key=2 output.txt permet alors d'afficher les lignes du fichier output.txt par deuxième mot croissant (dans l'ordre numérique). (Pour plus de détails sur la commande sort, exécuter man sort.)
On peut aussi obtenir directement la sortie triée par java Assoc | sort --numeric-sort --key=2. (En unix, la syntaxe com1 | com2 indique de rediriger la sortie de la commande com1 comme l'entrée de la commande com2.)
Nous allons maintenant encapsuler une liste d'association dans une
nouvelle classe TableAssoc :
class TableAssoc
{
Assoc l ;
TableAssoc () {
l = null ;
}
}
Écrire des méthodes non statiques pour ajouter une association dans
une table (put), récupérer la valeur associée à une clé
(get), tester s'il existe une association de clé donnée
(containsKey), et afficher toutes les associations d'une
table (print). (On utilisera au maximum le code déjà
écrit à la question précédente.)
Écrivez vos méthodes de sorte que les
statistiques sur les prénoms puissent se faire par :
public static void main (String[] args) {
TableAssoc t = new TableAssoc () ;
for (ListeEleve e = ListeEleve.toutInf421 ; e != null ; e = e.suivant) \{
if (t.containsKey (e.prenom)) {
int nb = t.get(e.prenom) ;
t.put (e.prenom, nb+1) ;
} else {
t.put (e.prenom, 1) ;
}
}
t.print () ;
}
Dans cette partie, nous allons utiliser l'implémentation de java des tables de hachage. Il y a donc beaucoup d'explications à lire et peu de code à taper...
Une table de hachage est en effet une structure plus efficace pour
retrouver les associations déjà insérées.
Java fournit une structure de table de hachage par la
classe java.util.Hashtable.
Pour avoir accès à toutes les classes de java.util, votre programme doit commencer par la ligne :
import java.util.* ;
On peut ensuite obtenir une nouvelle table de hachage par :
Hashtable t = new Hashtable () ;
(Sans le import java.util.* ;, il faudrait taper
java.util.Hashtable t = new java.util.Hashtable () ;...)
L'utilisation de Hashtable est similaire à la classe
TableAssoc que vous avez définit en question 2, sauf
qu'elle est conçue pour pouvoir gérer n'importe quel type de clés et
de valeurs. Elle contient ainsi des méthodes put,
get et containsKey de fonctionalité
similaire à celles que vous avez définit pour Table avec
les signatures suivantes :
Object put (Object key, Object value)
Object get (Object key)
boolean containsKey (Object key)
En java, toute les classes sont des cas particuliers de la classe
Object. Ainsi on peut sans problème utiliser une
String comme s'il s'agissait d'un Object, ce
qui permet d'écrire t.containsKey ("John"), par
exemple, sans que cela ne pose de problème. L'explication est très
simple : tous les objets sont des « flèches »,
c'est-à-dire des adresses mémoire pour l'ordinateur. Rien n'empêche
de considérer l'adresse d'une String comme étant
l'adresse d'un Object (tant qu'on est sûr que cela ne
peut pas provoquer d'erreur). Vous pouvez consulter la documentation
de la classe Object
et découvrir toutes les choses qui sont définies par défaut pour tout
objet (y compris pour vos propres classes).
Par contre, les int ne sont pas des objets et le
compilateur n'acceptera pas l'instruction t.put ("John",
9). Pour cela, java possède une classe Integer
qui définit un objet contenant un int. On pourra ainsi
effectuer t.put ("John", new Integer (9))
La transformation de Integer en Object ne
pose pas non plus de problème. Par contre l'inverse n'est pas permis à
priori. Ainsi il faudra écrire Object v = t.get
("John"), puis Integer vi = (Integer) v pour
demander de transformer
l'adresse v en une adresse vi
vers un Integer.
Si jamais l'objet pointé par v
n'est pas un Integer,
on obtiendra une erreur au moment de
l'exécution de la conversion. On peut bien sûr écrire directement
Integer vi = (Integer) t.get ("John").
Enfin, on peut obtenir la valeur int d'un Integer
vi par vi.intValue ().
Enfin, pour afficher toutes les associations d'une Hashtable,
on peut utiliser sa méthode String toString () qui renvoie une chaîne de caractère formée d'une suite de couples clé=valeur séparés par des virgules.
Reprenez la fonction main de la question 2 dans
une classe UtilTable en utilisant java.util.Hashtable.
Pour obtenir la présentation voulue
lors de l'affichage de la table (pour pouvoir utiliser
sort), nous avons besoin
de passer en revue toutes les associations de la table.
Pour cela, la méthode Enumeration keys () renvoie un objet de type
Enumeration.
Enumeration est une interface qui donne
les méthodes génériques pour parcourir tous les éléments d'une structure par un for de la manière suivante :
for (Enumeration e = t.keys () ; e.hasMoreElements () ; ) {
System.out.println (e.nextElement ()) ;
}
t.keys() renvoie une énumération fraîche des clés
de la table t positionnée sur la première clé.
e.hasMoreElements() renvoie vrai s'il y a au moins un
élément à passer en revue. e.nextElement()
renvoie l'élément courant (de type Object)
et positionne l'énumération sur l'élément suivant.
Pour info, voici à quoi ressemble le code source de
Enumeration :
interface Enumeration
{
public boolean hasMoreElements() ;
public Object nextElement() ;
}
Écrire une méthode qui affiche les associations de la table de hachage sous la forme :
Julien 2 Albert 3 Moi 1 ...
Pour vérifier l'efficacité des tables de hachage par rapport aux
listes d'associations, tester les deux méthodes sur l'annuaire de
l'École donné par la liste Annuaire.tout dans Annuaire.java.
On utilisera TC.demarrerChrono() et
TC.tempsChrono() pour mesurer le temps nécessaire
à l'insertion de tous les prénom de la liste.
Pour éviter de compter le temps de chargement de la liste,
on effectuera des mesures selon le schéma suivant :
ListeEleve charger = Annuaire.tout ;
TC.demarrerChrono () ;
// Insérer tous les prénoms.
System.out.println ("Temps d'insertion = " + TC.tempsChrono () + "ms") ;
Pour étudier le comportement asymptotique, effectuer des tests en ajoutant les prénoms de la liste 1 fois, 10 fois, 100 fois, ... Expliquez les résultats que vous observez.
Déposez vos fichiers en utilisant la ligne de commande :
/users/profs/info/Depot/INF_421/deposer vos_fichiers_java TD_3 votre_groupe
où vos_fichiers_java est la liste des fichiers que vous déposez (séparés par des espaces) et votre_groupe est votre numéro de groupe en informatique (entre 1 et 6).
Quelques exercices de plus.