Le but de cette séance est de manipuler différentes collections d’objets de façon à découvrir quelle collection est la plus adaptée pour répondre à un problème donné.
On manipulera des collections de Point. Nous vous proposons d’utiliser la version disponible ici .
Réalisez toutes les questions suivantes avec à la fois ArrayList et LinkedList et comparez leurs temps d’exécution.
1) Est-il possible d’ajouter plusieurs points identiques à une liste de type ArrayList(resp. LinkedList) ? Vérifiez votre réponse en testant.
2) Écrivez la méthode suivante qui permet de créer une liste de type ArrayList contenant n points de coordonnées tirées aléatoirement dans l’intervalle [0, range]. Faites une autre méthode créant une LinkedList.
public static List<Point> createRandom(int n, int range) {
Random random = new Random();
// todo, use random.nextInt(range)
}
3) Dans le programme principal, créez une liste de 10,000 points de coordonnées comprises entre 0 et 100 et écrivez trois versions différentes du code pour translater chacun des points d’un vecteur (-50, 50) : boucle for avec accès indicé à chacun des points, parcours de la liste avec itérateur, enhanced for loop. Quelle version est-elle préférable?
4) Évaluez le temps nécessaire pour modifier 100,000 fois le point situé au milieu de la liste. Vous pourrez utiliser la fonction suivante pour mesurer le temps.
long start = System.nanoTime();
// do some computation
long stop = System.nanoTime();
System.out.println("Elapsed time : " + (stop - start) / 1000);
5) Écrivez la méthode suivante qui permet de supprimer tous les points d’une liste qui sont situés dans le disque de centre c et de rayon r. Cette méthode retourne le nombre de points supprimés.
public static int removeInsideDisk(List<Point> l, Point c, int r) { /* todo */ }
6) Évaluez le temps d’exécution pour une liste de 1,000,000 points de coordonnées comprises entre -50 et 50 et pour le disque de centre (0, 0) et de rayon 50.
7) Écrivez deux versions d’une méthode qui crée une liste correspondant à l’entrelacement de deux listes : une version avec accès indicés, une version utilisant des itérateurs. Évaluez le temps d’exécution de chacune des deux versions.
8) Créez une liste de points et écrivez le code nécessaire pour la trier en utilisant la méthode sort de la classe Collections:
static <T> void sort(List<T> list, Comparator<? super T> c)
La méthode compare de l’interface Comparatorprend deux paramètres. Elle renvoie un entier soit négatif, soit nul, soit positif, suivant que le premier paramètre est inférieur, égal ou supérieur au second paramètre. Pour plus de détail sur ce que doit vérifier cette méthode, consultez la documentation. Un point sera dit inférieur à un autre si son abscisse est inférieure. En cas d’égalité des abscisses, on comparera les ordonnées.
Remarque
Pour utiliser la méthode, sort il est nécessaire de créer une nouvelle classe MyComparator qui implémente l’interface Comparator puis de créer une instance de cette classe. L’appel de la méthode sort ressemblerait à ceci :
public class MyComparator implements Comparator<Point> {
public int compare(Point p1, Point p2) {
// TODO
return 0;
}
}
sort(l, new MyComparator<Point>());
Pour simplifier ce cas assez fréquent, il est possible d’utiliser des classes anonymes. La syntaxe est la suivante :
sort(l, new Comparator<Point>() {
public int compare(Point p1, Point p2) {
// TODO
return 0;
}
});
Le principe est qu’on instancie un objet d’une classe anonyme (le compilateur générera automatiquement un nom) qui implémente l’interface Comparator<Point>. Il est possible d’utiliser la même syntaxe pour une classe anonyme fille d’une classe donnée.
9) Écrivez une version équivalente sans instancier de nouvel objet en utilisant les fonctions lambdas.
Créez une nouvelle collection de type TreeSet<Point>.
Set<Point> set = new TreeSet<>();
1) Essayer d’ajouter un point : set.add(new Point(0,0));
2) Que doit vérifier la classe Point pour que cette opération soit possible? Pourquoi? Faites les modifications nécessaires.
3) Ajoutez à l’ensemble set 10,000 points à coordonnées entières choisies aléatoirement dans l’intervalle [0, 100]. Quelle est la taille de l’ensemble après les ajouts?
4) Rappelez la spécificité du type Set qui explique le résultat.
On veut sélectionner une sous-partie des points d’une collection (et créer une nouvelle collection contenant ces points) à partir de plusieurs critères différents : points situés dans un disque, points situés dans un rectangle, points de coordonnées positives, points d’abscisse supérieure à une valeur donnée… Comment organiser le code de façon à ce que l’ajout d’un nouveau critère de sélection ne nécessite que l’écriture du critère lui-même?
On propose la méthode générique suivante :
public static <T> void selection(Collection<T> collIn, Collection<T> collOut, Predicate<T> f){
for (T e : collIn){
if (f.test(e))
collOut.add(e);
}
}
Utilisez-la avec des collections de points de votre choix en implémentant au moins deux des critères de sélection listés ci-dessus.
Téléchargez et décompressez l’archive expert.zip.
Lancez les 2 programmes principaux contenus dans les classes DemoMap.java et AnotherDemo.java.
1) Que constatez-vous en lançant ces 2 programmes ?
2) Quels problèmes pouvez-vous déceler ?
3) Comment y remédier ?
4) Modifiez les programmes en conséquence.