Le but de ce TP sera d'utiliser les collections java pour résoudre un problème concret de différentes manières et de voir qu'en utilisant des collections différentes on pourra avoir le même résultat mais qu'au niveau performance il y aura des différentes clairement visibles.
On cherche à travailler sur l'ensemble des mots en Français, voici une liste des mots à télécharger : ici
Avec cette liste des mots du Français, on souhaite pouvoir chercher efficacement si un mot est présent dans la liste.
Pour cela, on va utiliser les différentes collections Java pour répondre à cette question.
Partie 1 : Liste
Commencons tout d'abord par une liste. Vous devez réaliser la classe ListOfWords qui fonctionnera avec le code suivant :
import java.util.ArrayList;
public class App {
public static void main(String[] args) throws Exception {
int nbElements=10000;
ListOfWords lWords=new ListOfWords();
ArrayList<String> l= lWords.randomSelect(nbElements);
for(String s : l){
//System.out.println(s);
}
long start=System.currentTimeMillis();
ArrayList<String> lfound = lWords.find(l);
long end=System.currentTimeMillis();
long timeElapsed = end - start;
for(String s : lfound){
//System.out.println(s);
}
System.out.println("time with List "+timeElapsed);
}
}Le constructueur de ListOfWords doit lire le fichier des mots et mettre les mots dans une liste.
La méthode randomSelect sélectionne aléatoirement nbElements mots et les retourne dans un liste.
La méthode find prend une liste de mots en entrée et retourne une autre liste qui contient les mêmes mots suivis de "yes" ou de "no" selon que le mot est dans la liste de ListOfWords ou non.
Partie 2 : Table de hachage
Ensuite on va créer une classe HashOfWords pour réaliser la même tâche. Ainsi on va utiliser une table de hachage avec du type HashMap<Integer,String>. Pour calculer la clé, on utilisera la fonction hashCode() sur un String.
Le code sera le suivant :
import java.util.ArrayList;
public class App {
public static void main(String[] args) throws Exception {
int nbElements=10000;
ListOfWords lWords=new ListOfWords();
ArrayList<String> l= lWords.randomSelect(nbElements);
for(String s : l){
//System.out.println(s);
}
long start=System.currentTimeMillis();
ArrayList<String> lfound = lWords.find(l);
long end=System.currentTimeMillis();
long timeElapsed = end - start;
for(String s : lfound){
//System.out.println(s);
}
System.out.println("time with List "+timeElapsed);
HashOfWords hWords=new HashOfWords();
start=System.currentTimeMillis();
lfound = hWords.findValuesList(l);
end=System.currentTimeMillis();
timeElapsed = end - start;
System.out.println("time with HashMap values List "+timeElapsed);
start=System.currentTimeMillis();
lfound = hWords.findValuesToSet(l);
end=System.currentTimeMillis();
timeElapsed = end - start;
System.out.println("time with HashMap values converted to Set "+timeElapsed);
start=System.currentTimeMillis();
lfound = hWords.findKeys(l);
end=System.currentTimeMillis();
timeElapsed = end - start;
/*for(String s : lfound){
System.out.println(s);
}*/
System.out.println("time with HashMap keys "+timeElapsed);
}
}
Pour chercher si les mots sont présents dans la tache de hachage, on va écrire 3 méthodes différentes.
Partie 3 : Comparaison des versions des tables de hachage
On va tester les 3 types de table de hachage de Java avec le code suivant.
Vous devez modifier légèrement votre code pour executer le code. La valeur nbElements=100000 est mise pour pouvoir constater une différence au niveau de l'exécution du code. Vous pouvez la changer.
import java.util.ArrayList;
public class App {
public static void main(String[] args) throws Exception {
int nbElements=100000;
ListOfWords lWords=new ListOfWords();
ArrayList<String> l= lWords.randomSelect(nbElements);
for(String s : l){
//System.out.println(s);
}
long start=System.currentTimeMillis();
ArrayList<String> lfound = lWords.find(l);
long end=System.currentTimeMillis();
long timeElapsed = end - start;
for(String s : lfound){
//System.out.println(s);
}
System.out.println("time with List "+timeElapsed);
for (int i=0;i<3;i++) {
HashOfWords hWords=new HashOfWords(i);
switch(i) {
case 0: System.out.println("HashMap"); break;
case 1: System.out.println("TreeMap"); break;
case 2: System.out.println("LinkedHashMap"); break;
}
start=System.currentTimeMillis();
lfound = hWords.findValuesList(l);
end=System.currentTimeMillis();
timeElapsed = end - start;
System.out.println("time with HashMap values List "+timeElapsed);
start=System.currentTimeMillis();
lfound = hWords.findValuesToSet(l);
end=System.currentTimeMillis();
timeElapsed = end - start;
System.out.println("time with HashMap values converted to Set "+timeElapsed);
start=System.currentTimeMillis();
lfound = hWords.findKeys(l);
end=System.currentTimeMillis();
timeElapsed = end - start;
/*for(String s : lfound){
System.out.println(s);
}*/
System.out.println("time with HashMap keys "+timeElapsed);
}
}
}