Chapitre 9 - Stockage des objets

Les solutions d'exercices sélectionnés peuvent être trouvées dans le document électronique The Thinking in Java Annotated Solution Guide, disponible pour un faible coût sur www.BruceEckel.com.

1. Créez un tableau de doubles et remplissez-le avec fill() en utilisant RandDoubleGenerator. Affichez les résultats.
2. Créez une nouvelle classe Gerbil possédant un int gerbilNumber initialisé dans le constructeur (similaire à l'exemple Mouse de ce chapitre). Donnez-lui une méthode hop() qui affiche son numéro de gerboise et un message indiquant qu'elle est en train de sauter. Créez une ArrayList et ajoutez-y un ensemble d'objets Gerbil. Maintenant utilisez la méthode get() pour parcourir la List et appelez hop() pour chaque Gerbil.
3. Modifiez l'exercice 2 afin d'utiliser un Iterator lors du parcours de la List pour appeler hop().
4. Prenez la classe Gerbil de l'exercice 2 et placez-la dans une Map à la place, en associant le nom (une String) de la Gerbil à chaque Gerbil (la valeur) stockée dans la table. Récupérer un Iterator sur l'ensemble des clefs (obtenu via keySet()) et utilisez-le pour parcourir la Map, récupérez la Gerbil pour chaque clef, imprimez son nom et dites-lui de sauter avec la méthode hop().
5. Créez une List (essayez avec une ArrayList et une LinkedList) et remplissez-la en utilisant Collections2.countries. Triez cette liste et affichez-la, puis appliquez-lui Collections.shuffle() plusieurs fois, en l'imprimant à chaque fois pour voir les effets de cette méthode.
6. Montrez que vous ne pouvez ajouter que des objets Mouse dans une MouseList.
7. Modifiez MouseList.java de manière à ce qu'elle hérite de ArrayList au lieu d'utiliser la composition. Illustrez le problème de cette approche.
8. Réparez CatsAndDogs.java en créant un conteneur Cats (en utilisant ArrayList) qui n'accepte que des objets Cats.
9. Créez un conteneur qui encapsule un tableau de Strings, qui ne stocke et ne renvoie que des Strings, afin de ne pas avoir de transtypage à faire lorsqu'on l'utilise. Si le tableau interne n'est pas assez grand pour l'insertion suivante, le conteneur devra se redimensionner automatiquement. Dans main(), comparez les performances de votre conteneur avec une ArrayList contenant des Strings.
10. Répétez l'exercice 9 pour un conteneur d'ints, et comparez les performances avec une ArrayList contenant des objets Integer. Dans le test de performances, incluez en plus le fait d'incrémenter chaque objet du conteneur.
11. Créez un tableau pour chaque type primitif et un tableau de Strings, remplissez chaque tableau en utilisant un générateur fourni parmi les utilitaires de com.bruceeckel.util, et afficher chaque tableau en utilisant la méthode print() appropriée.
12. Créez un générateur qui produise des noms de personnages de vos films préférés (que pensez-vous de Snow White ou Star Wars), et revienne au début quand il n'a plus de noms à proposer. Utilisez les utilitaires de com.bruceeckel.util pour remplir un tableau, une ArrayList, une LinkedList et les deux types de Set disponibles, puis imprimez chaque conteneur.
13. Créez une classe contenant deux objets String, et rendez-la Comparable afin que la comparaison ne porte que sur la première String. Remplissez un tableau et une ArrayList avec des objets de cette classe, en utilisant le générateur geography. Montrez que le tri fonctionne correctement. Créez maintenant un Comparator qui porte sur la deuxième String, et montrez que le tri fonctionne aussi ; effectuez une recherche en utilisant votre Comparator.
14. Modifiez l'exercice 13 afin d'utiliser un tri alphabétique.
15. Utilisez Arrays2.RandStringGenerator pour remplir un TreeSet utilisant un tri alphabétique. Imprimez le TreeSet pour vérifier l'ordre.
16. Créez une ArrayList et une LinkedList, et remplissez-les en utilisant le générateur Collections2.capitals. Imprimez chaque liste en utilisant un Iterator ordinaire, puis insérer une liste dans l'autre en utilisant un ListIterator, en insérant un élément de la deuxième liste entre chaque élément de la première liste. Réalisez maintenant cette insertion en partant de la fin de la première liste et en la parcourant à l'envers.
17. Ecrivez une méthode qui utilise un Iterator pour parcourir une Collection et imprime le code de hachage de chaque objet du conteneur. Remplissez tous les types de Collections existants avec des objets et utilisez votre méthode avec chaque conteneur.
18. Réparez le problème d'InfiniteRecursion.java.
19. Créez une classe, puis créez un tableau d'objets de votre classe. Remplissez une List à partir du tableau. Créez un sous-ensemble de la List en utilisant subList(), puis supprimez cet ensemble de la List avec removeAll().
20. Modifiez l'exercice 6 du Chapitre 7 afin de stocker les Rodents dans une ArrayList et utilisez un Iterator pour parcourir la séquence des Rodents. Rappelez-vous qu'une ArrayList ne stocke que des Objects et qu'on doit donc les transtyper pour retrouver le comportement d'un Rodent.
21. En vous basant sur Queue.java, créez une classe DoubleFile et testez-la.
22. Utilisez un TreeMap dans Statistics.java. Ajoutez maintenant du code afin de tester les différences de performances entre HashMap et TreeMap dans ce programme.
23. Créez une Map et un Set contenant tous les pays dont le nom commence par un 'A'.
24. Remplissez un Set à l'aide de Collections2.countries, utilisez plusieurs fois les mêmes données et vérifiez que le Set ne stocke qu'une seule instance de chaque donnée. Testez ceci avec les deux types de Set.
25. A partir de Statistics.java, créez un programme qui lance le test plusieurs fois et vérifie si un nombre a tendance à apparaître plus souvent que les autres dans les résultats.
26. Réécrivez Statistics.java en utilisant un HashSet d'objets Counter (vous devrez modifiez la classe Counter afin qu'elle fonctionne avec un HashSet). Quelle approche semble la meilleure ?
27. Modifiez la classe de l'exercice 13 afin qu'elle puisse être stockée dans un HashSet et comme clef dans un HashMap.
28. Créez un SlowSet en vous inspirant de SlowMap.java.
29. Appliquez les tests de Map1.java à SlowMap pour vérifier que cette classe fonctionne. Corrigez dans SlowMap tout ce qui ne marche pas correctement.
30. Implémentez le reste de l'interface Map pour SlowMap.
31. Modifiez MapPerformance.java afin d'inclure les tests pour SlowMap.
32. Modifiez SlowMap afin qu'elle utilise une seule ArrayList d'objets MPair au lieu de deux ArrayLists. Vérifiez que la version modifiée fonctionne correctement. Utilisez MapPerformance.java pour tester cette nouvelle Map. Modifiez maintenant la méthode put() afin qu'elle effectue un sort() après chaque insertion, et modifiez get() afin d'utiliser Collections.binarySearch() pour récupérer la clef. Comparez les performances de la nouvelle version avec les anciennes.
33. Ajoutez un champ char à CountedString qui soit aussi initialisé dans le constructeur, et modifiez les méthodes hashCode() et equals() afin d'inclure la valeur de ce char.
34. Modifiez SimpleHashMap afin de signaler les collisions, et testez ce comportement en ajoutant les mêmes données plusieurs fois afin de voir les collisions.
35. Modifiez SimpleHashMap afin de signaler le nombre d'objets testés lorsqu'une collision survient. Autrement dit, combien d'appels à next() doivent être effectués sur l'Iterator parcourant la LinkedList pour trouver l'occurence recherchée ?
36. Implémentez les  méthodes clear() et remove() pour SimpleHashMap.
37. Implémentez le reste de l'interface Map pour SimpleHashMap.
38. Ajoutez une méthode private rehash() à SimpleHashMap qui soit invoquée lorsque le facteur de charge dépasse 0,75. Au cours du rehachage, doublez le nombre de seaux et recherchez le premier nombre premier qui soit supérieur à cette valeur pour déterminer le nouveau nombre de seaux.
39. Créez et testez un SimpleHashSet en vous inspirant de SimpleHashMap.java.
40. Modifiez SimpleHashMap afin d'utiliser des ArrayLists au lieu de LinkedLists. Modifiez MapPerformance.java afin de comparer les performances des deux implémentations.
41. Consultez la documentation HTML du JDK (téléchargeable sur java.sun.com) de la classe HashMap. Créez un HashMap, remplissez-le avec des éléments et déterminez son facteur de charge. Testez la vitesse d'accès aux éléments de ce dictionnaire ; essayez d'augmenter cette vitesse en créant un nouveau HashMap d'une capacité initiale supérieure et en copiant l'ancien dictionnaire dans le nouveau.
42. Dans le Chapitre 8, localisez l'exemple GreenHouse.java comportant 3 fichiers. Dans Controller.java, la classe EventSet n'est qu'un conteneur. Changez le code afin d'utiliser une LinkedList au lieu d'un EventSet. Remplacer EventSet par LinkedList ne suffira pas, il vous faudra aussi utiliser un Iterator pour parcourir l'ensemble d'événements.
43. (Difficile). Créez votre propre classe de dictionnaire haché, particularisée pour un type particulier de clefs : String par exemple. Ne la faites pas dériver de Map. A la place, dupliquez les méthodes afin que les méthodes put() et get() n'acceptent que des objets String comme clef, et non des Objects. Tout ce qui touche les clefs ne doit pas impliquer de types génériques, mais uniquement des Strings afin d'éviter les surcoûts liés au transtypage. Votre but est de réaliser l'implémentation la plus rapide possible. Modifiez MapPerformance.java afin de tester votre implémentation contre un HashMap.
44. (Difficile). Trouvez le code source de List dans la bibliothèque de code source Java fournie dans toutes les distributions Java. Copiez ce code et créez une version spéciale appelée intList qui ne stocke que des ints. Réfléchissez à ce qu'il faudrait pour créer une version spéciale de List pour chacun des types scalaires. Réfléchissez maintenant à ce qu'il faudrait si on veut créer une classe de liste chaînée qui fonctionne avec tous les types scalaires. Si les types paramétrés sont implémentés un jour dans Java, ils fourniront un moyen de réaliser ce travail automatiquement (entre autres).

[44]Il est toutefois possible de s'enquérir de la taille du vector, et la méthode at() effectue, elle, un contrôle sur les indices.

[45]C'est l'un des points où le C++ est indiscutablement supérieur à Java, puisque le C++ supporte la notion de types paramétrés grâce au mot-clef template.

[46]Le programmeur C++ remarquera comme le code pourrait être réduit en utilisant des arguments par defaut et des templates. Le programmeur Python, lui,  notera que cette bibliothèque est complètement inutile dans ce langage.

[47]Par Joshua Bloch de chez Sun.

[48]Ces données ont été trouvées sur Internet, et parsées ensuite par un programme Python (cf. www.Python.org).

[49]Voici un endroit où la surcharge d'opérateur serait appréciée.

[50]Si ces accélérations ne suffisent pas pour répondre aux besoins de performance du programme, il est toujours possible d'accélérer les accès en implémentant une nouvelle Map et en la particularisant pour le type spécifique destiné à être stocké pour éviter les délais dûs au transtypage en Object et inversement. Pour atteindre des niveaux encore plus élevés de performance, les fanas de vitesse pourront se référer à The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition de Donald Knuth pour remplacer les listes par des tableaux qui possèdent deux avantages supplémentaires : leurs caractéristiques peuvent être optimisées pour le stockage sur disque et ils peuvent économiser la plus grande partie du temps passée à créer et détruire les enregistrements individuels.