Activité Rechercher dans une liste avec un index
Situation
On vous demande de réaliser une application pour rechercher une personne dans une liste en fonction de son nom. Vous constatez que les temps de recherche dépendent directement du nombre d’éléments dans la liste. Vous décidez d’étudier la notion d’index pour trouver un moyen d’améliorer cette situation.
Consigne
Pour ce travail, on vous demande de réaliser les tâches décrites ci-après.
Objectif
À la fin de ce travail, vous devez :
- Connaître la notion d’index.
Résultat attendu
Un compte rendu de l’activité et les réponses aux questions posées dans une section de votre rapport du module.
Ressources
Documents :
- Fichier de données : data.xml
- Code de l’activité précédente
Logiciel :
- NetBeans
Trier les données selon le critère de recherche
Reprenez le projet ContactManager de l’activité précédente et vérifiez qu’il fonctionne correctement.
La première étape pour accélérer la recherche consiste à trier les données selon le critère de recherche (dans notre cas le nom). De cette manière, dès qu’une personne est trouvée, on sait que toutes les autres personnes qui ont le même nom se trouve immédiatement après et qu’on peut arrêter la recherche dès qu’on trouve un personne dont le nom est différent.
Pour réaliser cela, on doit commencer par réaliser une fonction pour trier la liste. Pour évider de modifier la liste existante, on va réaliser une fonction qui prend une liste en paramètre et qui renvoie une copie triée de cette liste. Ajouter la fonction de la figure 1 au code de votre programme.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Copie la liste passée en paramètre, trie les éléments de la copie et renvoie la copie triée.
*
* Remarque :
* Cette fonction implémente un tri par bulle facile à comprendre mais particulièrement
* lent qui n'est jamais utilisé pour trier un grand nombre de données.
*
* @param personList la liste à trier
* @return une copie de la liste triée
*/
private static List<Person> sortByName(List<Person> personList) {
Person[] personArray = personList.toArray(new Person[0]);
for (int i = personArray.length - 1; i >= 1; i -= 1) {
for (int j = 0; j <= i - 1; j += 1) {
if (personArray[j + 1].lastname.compareTo(personArray[j].lastname) < 0) {
Person tmp = personArray[j + 1];
personArray[j + 1] = personArray[j];
personArray[j] = tmp;
}
}
}
return Arrays.asList(personArray);
}
Ajouter ensuite la fonction findPersonByName2. Cette fonction est presque identique à findPersonByName1, mais elle arrête la recherche lorsqu’une personne ne correspond pas au critère de recherche et qu’une ou plusieurs personnes ont déjà été trouvées.
s
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
* Cherche dans une liste de personnes, les personnes dont le nom est celui
* passé en paramètre et renvoie la liste des personnes trouvées.
* Si aucune personne n’a été trouvée, la fonction renvoie une liste vide.
*
* @param personList la liste de personn
* @param name le nom de la personne recherchée
* @return l’objet correspondant à la personn
*/
private static List<Person> findPersonByName2(List<Person> personList, String name) {
// Crée un nouveau tableau dynamique pour y stocker les
// personnes qui correspondent au critère de recherche
List<Person> result = new ArrayList<>();
// Initialise un drapeau pour indiquer qu’une personne
// correspondant au critère a été trouvée.
boolean personFound = false;
// Répète pour chaque personne de la liste.
for (int i = 0; i < personList.size(); i += 1) {
// Récupère l’objet de type Person.
Person person = personList.get(i);
// Teste si le nom de la personne correspond
// à celui passé en paramètre.
if (person.lastname.equals(name)) {
// Ajoute la personne à la liste des
// personnes trouvées.
result.add(person);
// Indique qu’une personne a été trouvée.
personFound = true;
} else {
// Arrête la recherche si une personne qui correspond
// au critère a déjà été trouvée.
if (personFound) {
break;
}
}
}
// Renvoie la liste des personnes trouvées.
return result;
}
Enfin, modifier la procédure main pour ajouter l’appel à la fonction de tri et utiliser la liste triée dans l’appel de la fonction findPersonByName2.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public static void main(String[] args) throws Exception {
// Initialise une chaîne de caractère avec le chemin du fichier XML.
// Attention : Les backslashes (\) du chemin Windows sont dédoublés
// car dans une chaîne de caractères, le backslash est le caractère
// d’échappement qui permet d’écrire des caractères spéciaux tels que
// \r (carriage return), \n (line feed) ou \t (tab).
String filename = "/Users/frossardj/Documents/data.xml"; //"C:\\Users\\frossardj\\Documents\\data.xml";
// Crée un objet de type File avec le chemin du fichier XML.
File xmlFile = new File(filename);
// Charge les données des personnes qui se trouve dans le fichier XML
// dans un objet de type List de Person et affecte une référence à cet
// objet à la variable personList.
List<Person> personList = loadPersonDataFromXml(xmlFile);
// Création d'un index.
// Dans cet exemple, l'index est simplement une nouvelle liste
// triée selon le nom (lastname). Il pourrait s'agir d'une
// structure plus complexe comme un arbre ou une table de hachage.
List<Person> personListSortedByName = sortByName(personList);
// Demande à l’utilisateur de saisir le nom de la personne recherchée.
System.out.printf("Veuillez saisir le nom d’une person : ");
Console console = System.console();
String name = console.readLine();
// Mesure le temps avant l’exécution
long startTime = System.nanoTime();
// Recherche les personnes dans liste triée.
List<Person> result = findPersonByName3(personListSortedByName, name);
// Mesure le temps après l’exécution
long endTime = System.nanoTime();
// Affiche le résultat dans la sortie standard (System.out).
printPersonList(System.out, result);
// Affiche le temps d’exécution
System.out.printf("\nTemps d’exécution : %d ns\n", endTime - startTime);
}
Questions
Avant d’aller plus loin, répondez au deux questions suivantes :
- Mesurez 5 ou 6 fois le temps d’exécution de la recherche avec le nom Alexander, calculez la moyenne et refaites l’expérience avec les noms Walker et Skywalker. Que constatez-vous ?
- Comment expliquez-vous les différences de temps ?
Recherche dichotomique
Vous avez pu constater que le fait de trier la liste améliore le temps de recherche, mais uniquement pour certaines valeurs. Pour améliorer le temps pour toutes les valeurs, il faut essayer de faire en sorte que le nombre de valeurs à tester soit à peu près le même, quelle que soit la valeur du critère. On peut parvenir à ce résultat avec une recherche dichotomique.
Lisez la description de cette recherche ajoutez la fonction findPersonByName3 conformément au code de la figure 5.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/**
* Cherche dans une liste de personnes, les personnes dont le nom est celui passé en
* paramètre et renvoie la liste des personnes trouvées.
* Si aucune personne n’a été trouvée, la fonction renvoie une liste vide.
*
* Cette fonction suppose que la liste est triée et effectue une recherche dichotomique.
*
* @param personList la liste de personnes
* @param name le nom de la personne recherchée
* @return l’objet correspondant à la personne
*/
private static List<Person> findPersonByName3(List<Person> personList, String name) {
// Crée un nouveau tableau dynamique pour y stocker les
// personnes qui correspondent au critère de recherche
List<Person> result = new ArrayList<>();
// Initialise un drapeau pour indiquer qu’une personne
// correspondant au critère a été trouvée.
boolean personFound = false;
int low = 0;
int high = personList.size();
int middle;
int start = high;
while (low <= high) {
// Prend la personne au milieu de la liste.
middle = low + ((high - low) / 2);
Person person = personList.get(middle);
// Compare le nom de la personne au nom recherché.
int comp = person.lastname.compareTo(name);
if (comp > 0) {
// Si le nom de la personne se trouve après
// le nom recherché, recommence avec la moitié
// supérieure de la liste.
high = middle - 1;
} else if (comp < 0) {
// Si le nom de la personne se trouve avant
// le nom recherché, recommence avec la moitié
// inférieure de la liste.
low = middle + 1;
} else {
// Si le nom de la personne correspond au nom
// recherché, arrête la recherche.
start = middle;
break;
}
}
// Répète pour chaque personne de la liste à partir de
// la postion de départ donnée par l’index.
for (int i = start; i < personList.size(); i += 1) {
// Récupère l’objet de type Person.
Person person = personList.get(i);
// Teste si le nom de la personne correspond
// à celui passé en paramètre.
if (person.lastname.equals(name)) {
// Ajoute la personne à la liste des
// personnes trouvées.
result.add(person);
// Indique qu’une personne a été trouvée.
personFound = true;
} else {
// Si une personne correspondant au critère
// a été trouvée, arrête la recherche.
if (personFound) {
// sort de la boucle
break;
}
}
}
// Renvoie la liste des personnes trouvées.
return result;
}
}
Enfin, modifiez la procédure principale pour appeler la fonction findPersonByName3 (voir figure 6).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public static void main(String[] args) throws Exception {
// Initialise une chaîne de caractère avec le chemin du fichier XML.
// Attention : Les backslashes (\) du chemin Windows sont dédoublés
// car dans une chaîne de caractères, le backslash est le caractère
// d’échappement qui permet d’écrire des caractères spéciaux tels que
// \r (carriage return), \n (line feed) ou \t (tab).
String filename = "/Users/frossardj/Documents/data.xml"; //"C:\\Users\\frossardj\\Documents\\data.xml";
// Crée un objet de type File avec le chemin du fichier XML.
File xmlFile = new File(filename);
// Charge les données des personnes qui se trouve dans le fichier XML
// dans un objet de type List de Person et affecte une référence à cet
// objet à la variable personList.
List<Person> personList = loadPersonDataFromXml(xmlFile);
// Création d'un index.
// Dans cet exemple, l'index est simplement une nouvelle liste
// triée selon le nom (lastname). Il pourrait s'agir d'une
// structure plus complexe comme un arbre ou une table de hachage.
List<Person> personListSortedByName = sortByName(personList);
// Demande à l’utilisateur de saisir le nom de la personne recherchée.
System.out.printf("Veuillez saisir le nom d’une person : ");
Console console = System.console();
String name = console.readLine();
// Mesure le temps avant l’exécution
long startTime = System.nanoTime();
// Recherche les personnes dans liste triée.
List<Person> result = findPersonByName3(personListSortedByName, name);
// Mesure le temps après l’exécution
long endTime = System.nanoTime();
// Affiche le résultat dans la sortie standard (System.out).
printPersonList(System.out, result);
// Affiche le temps d’exécution
System.out.printf("\nTemps d’exécution : %d ns\n", endTime - startTime);
}
Questions
- Mesurez 5 ou 6 fois le temps d’exécution de la recherche avec le nom Alexander, calculez la moyenne et refaites l’expérience avec les noms Walker et Skywalker. Que constatez-vous ?
- Commentez les résultats.
- Que devrait-on faire si l’on voulait également permettre la recherche par le prénom ?
- Quelles sont les conséquences pour l’index si l’on ajoute ou si l’on supprime une personne dans la liste ?