Chapitre 9 - Stockage des objets

pages : 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Choisir la bonne Map

Lorsqu'on doit choisir entre les différentes implémentations d'une Map, sa taille est le critère qui affecte le plus les performances, et le programme de test suivant donne une indication des compromis :

//: c09:MapPerformance.java
// Illustre les différences de performance entre les Maps.
import java.util.*;
import com.bruceeckel.util.*;

public class MapPerformance {
  private abstract static class Tester {
    String name;
    Tester(String name) { this.name = name; }
    abstract void test(Map m, int size, int reps);
  }
  private static Tester[] tests = {
    new Tester("put") {
      void test(Map m, int size, int reps) {
        for(int i = 0; i < reps; i++) {
          m.clear();
          Collections2.fill(m,
            Collections2.geography.reset(), size);
        }
      }
    },
    new Tester("get") {
      void test(Map m, int size, int reps) {
        for(int i = 0; i < reps; i++)
          for(int j = 0; j < size; j++)
            m.get(Integer.toString(j));
      }
    },
    new Tester("iteration") {
      void test(Map m, int size, int reps) {
        for(int i = 0; i < reps * 10; i++) {
          Iterator it = m.entrySet().iterator();
          while(it.hasNext())
            it.next();
        }
      }
    },
  };
  public static void
  test(Map m, int size, int reps) {
    System.out.println("Testing " +
      m.getClass().getName() + " size " + size);
    Collections2.fill(m,
      Collections2.geography.reset(), size);
    for(int i = 0; i < tests.length; i++) {
      System.out.print(tests[i].name);
      long t1 = System.currentTimeMillis();
      tests[i].test(m, size, reps);
      long t2 = System.currentTimeMillis();
      System.out.println(": " +
        ((double)(t2 - t1)/(double)size));
    }
  }
  public static void main(String[] args) {
    int reps = 50000;
    // Le nombre de répétitions peut être spécifié
    // via la ligne de commande :
    if(args.length > 0)
      reps = Integer.parseInt(args[0]);
    // Petit :
    test(new TreeMap(), 10, reps);
    test(new HashMap(), 10, reps);
    test(new Hashtable(), 10, reps);
    // Moyen :
    test(new TreeMap(), 100, reps);
    test(new HashMap(), 100, reps);
    test(new Hashtable(), 100, reps);
    // Gros :
    test(new TreeMap(), 1000, reps);
    test(new HashMap(), 1000, reps);
    test(new Hashtable(), 1000, reps);
  }
} ///:~

Parce que la taille du dictionnaire constitue le facteur principal, les tests de chronométrage divisent le temps par la taille du dictionnaire pour normaliser chaque mesure. Voici un ensemble de résultats (les vôtres différeront probablement) :

Type	Test size	Put	Get	Iteration
	10	143.0	110.0	186.0
TreeMap	100	201.1	188.4	280.1
	1000	222.8	205.2	40.7
	10	66.0	83.0	197.0
HashMap	100	80.7	135.7	278.5
	1000	48.2	105.7	41.4
	10	61.0	93.0	302.0
Hashtable	100	90.6	143.3	329.0
	1000	54.1	110.95	47.3

Comme on pouvait s'y attendre, les performances d'une HashTable sont à peu près équivalentes à celles d'un HashMap (bien que ceux-ci soient généralement un petit peu plus rapides). Les TreeMaps étant généralement plus lents que les HashMaps, pourquoi voudrait-on les utiliser ? En fait, on les utilise non comme des Maps mais comme une façon de créer une liste ordonnée. Le comportement d'un arbre est tel qu'il est toujours ordonné et n'a pas besoin d'être spécifiquement trié. Une fois un TreeMap rempli, il est possible d'appeler keySet() pour récupérer un Set des clefs, puis toArray() pour produire un tableau de ces clefs. On peut alors utiliser la méthode static Arrays.binarySearch() (que nous étudierons plus loin) pour trouver rapidement des objets dans ce tableau trié. Bien sûr, on ne ferait ceci que si, pour une raison ou une autre, le comportement d'un HashMap ne convenait pas, puisqu'un HashMap est conçu justement pour retrouver rapidement des objets. De plus, on peut facilement créer un HashMap à partir d'un TreeMap avec une simple création d'objet. Pour résumer, votre premier réflexe si vous voulez utiliser une Map devrait être de se tourner vers un HashMap, et n'utiliser un TreeMap que si vous avez besoin d'une Map constamment triée.

Trier et rechercher dans les Lists

Les fonctions effectuant des tris et des recherches dans les Lists ont les mêmes noms et signature que celles réalisant ces opérations sur des tableaux d'objets, mais sont des méthodes static appartenant à la classe Collections au lieu de Arrays. En voici un exemple, adapté de ArraySearching.java :

//: c09:ListSortSearch.java
// Trier et rechercher dans les Lists avec 'Collections.'
import com.bruceeckel.util.*;
import java.util.*;

public class ListSortSearch {
  public static void main(String[] args) {
    List list = new ArrayList();
    Collections2.fill(list,
      Collections2.capitals, 25);
    System.out.println(list + "\n");
    Collections.shuffle(list);
    System.out.println("After shuffling: "+list);
    Collections.sort(list);
    System.out.println(list + "\n");
    Object key = list.get(12);
    int index =
      Collections.binarySearch(list, key);
    System.out.println("Location of " + key +
      " is " + index + ", list.get(" +
      index + ") = " + list.get(index));
    AlphabeticComparator comp =      new AlphabeticComparator();
    Collections.sort(list, comp);
    System.out.println(list + "\n");
    key = list.get(12);
    index =
      Collections.binarySearch(list, key, comp);
    System.out.println("Location of " + key +
      " is " + index + ", list.get(" +
      index + ") = " + list.get(index));
  }
} ///:~

L'utilisation de ces méthodes est identique à celles dans Arrays, mais une List est utilisée à la place d'un tableau. Comme pour les tableaux, il faut passer le Comparator utilisé pour trier la liste lorsqu'on fait un appel à binarySearch().

Ce programme illustre aussi la méthode shuffle() de la classe Collections, qui modifie aléatoirement l'ordre d'une List.

Utilitaires

Il existe un certain nombre d'autres méthodes bien pratiques dans la classe Collections :

enumeration(Collection)	Renvoie une Enumeration de l'argument.
max(Collection) min(Collection)	Renvoie l'élément maximum ou minimum de l'argument en utilisant la méthode de comparaison naturelle des objets de la Collection.
max(Collection, Comparator) min(Collection, Comparator)	Renvoie l'élément maximum ou minimum de la Collection en utilisant le Comparator.
reverse()	Inverse tous les éléments sur place.
copy(List dest, List src)	Copie les éléments de src vers dest.
fill(List list, Object o)	Remplace tous les éléments de la liste avec o.
nCopies(int n, Object o)	Renvoie une List non-modifiable de taille n dont les références pointent toutes sur o.

Notez que comme min() et max() fonctionnent avec des objets Collection, et non avec des Lists, il n'est pas nécessaire que celle-ci soit triée (ainsi que nous l'avons déjà vu, il faut trier une List ou un tableau avant de leur appliquer binarySearch()).

Rendre une Collection ou une Map non-modifiable

Il est souvent bien pratique de créer une version en lecture seule d'une Collection ou d'une Map. La classe Collections permet ceci en passant le conteneur original à une méthode qui en renvoie une version non modifiable. Il existe quatre variantes de cette méthode, pour les Collections (si on ne veut pas traiter une Collection comme un type plus spécifique), les Lists, les Sets et les Maps. Cet exemple montre la bonne manière pour construire des versions en lecture seule des collections :

//: c09:ReadOnly.java
// Utilisation des méthodes Collections.unmodifiable.
import java.util.*;
import com.bruceeckel.util.*;

public class ReadOnly {
  static Collections2.StringGenerator gen =
    Collections2.countries;
  public static void main(String[] args) {
    Collection c = new ArrayList();
    Collections2.fill(c, gen, 25); // Insertion des données
    c = Collections.unmodifiableCollection(c);
    System.out.println(c); // L'accès en lecture est OK
    c.add("one"); // Modification impossible

    List a = new ArrayList();
    Collections2.fill(a, gen.reset(), 25);
    a = Collections.unmodifiableList(a);
    ListIterator lit = a.listIterator();
    System.out.println(lit.next()); // L'accès en lecture est OK
    lit.add("one"); // Modification impossible

    Set s = new HashSet();
    Collections2.fill(s, gen.reset(), 25);
    s = Collections.unmodifiableSet(s);
    System.out.println(s); // L'accès en lecture est OK
    //! s.add("one"); // Modification impossible

    Map m = new HashMap();
    Collections2.fill(m,
      Collections2.geography, 25);
    m = Collections.unmodifiableMap(m);
    System.out.println(m); // L'accès en lecture est OK
    //! m.put("Ralph", "Howdy!");
  }
} ///:~

Dans chaque cas, le conteneur doit être rempli de données avant de le rendre non-modifiable. Une fois rempli, la meilleure approche consiste à remplacer la référence existante par la référence renvoyée par l'appel à « unmodifiable ». De cette façon, on ne risque pas d'en altérer accidentellement le contenu une fois qu'on l'a rendu non modifiable. D'un autre côté, cet outil permet de garder un conteneur modifiable private dans la classe et de renvoyer une référence en lecture seule sur ce conteneur à partir d'une méthode. Ainsi on peut le changer depuis la classe, tandis qu'on ne pourra y accéder qu'en lecture depuis l'extérieur de cette classe.

Appeler la méthode « unmodifiable » pour un type particulier n'implique pas de contrôle lors de la compilation, mais une fois la transformation effectuée, tout appel à une méthode tentant de modifier le contenu du conteneur provoquera une UnsupportedOperationException.

Synchroniser une Collection ou une Map

Le mot-clef synchronized constitue une partie importante du multithreading, un sujet plus compliqué qui ne sera abordé qu'à partir du Chapitre 14. Ici, je noterai juste que la classe Collections permet de synchroniser automatiquement un conteneur entier. La syntaxe en est similaire aux méthodes « unmodifiable » :

//: c09:Synchronization.java
// Utilisation des méthodes Collections.synchronized.
import java.util.*;

public class Synchronization {
  public static void main(String[] args) {
    Collection c =
      Collections.synchronizedCollection(
        new ArrayList());
    List list = Collections.synchronizedList(
      new ArrayList());
    Set s = Collections.synchronizedSet(
      new HashSet());
    Map m = Collections.synchronizedMap(
      new HashMap());
  }
} ///:~

Dans ce cas, on passe directement le nouveau conteneur à la méthode « synchronisée » appropriée ; ainsi la version non synchronisée ne peut être accédée de manière accidentelle.

Echec rapide

Les conteneurs Java possèdent aussi un mécanisme qui permet d'empêcher que le contenu d'un conteneur ne soit modifié par plus d'un processus. Le problème survient si on itère à travers un conteneur alors qu'un autre processus insère, supprime ou change un objet de ce conteneur. Cet objet peut déjà avoir été passé, ou on ne l'a pas encore rencontré, peut-être que la taille du conteneur a diminué depuis qu'on a appelé size() - il existe de nombreux scénarios catastrophes. La bibliothèque de conteneurs Java incorpore un mécanisme d'échec-rapide qui traque tous les changements effectués sur le conteneur autres que ceux dont notre processus est responsable. S'il détecte que quelqu'un d'autre tente de modifier le conteneur, il produit immédiatement une ConcurrentModificationException. C'est l'aspect « échec-rapide » - il ne tente pas de détecter le problème plus tard en utilisant un algorithme plus complexe.

Il est relativement aisé de voir le mécanisme d'échec rapide en action - tout ce qu'on a à faire est de créer un itérateur et d'ajouter alors un item à la collection sur laquelle l'itérateur pointe, comme ceci :

//: c09:FailFast.java
// Illustre la notion d'« échec rapide ».
import java.util.*;

public class FailFast {
  public static void main(String[] args) {
    Collection c = new ArrayList();
    Iterator it = c.iterator();
    c.add("An object");
    // Génére une exception :
    String s = (String)it.next();
  }
} ///:~

L'exception survient parce que quelque chose est stocké dans le conteneur après que l'itérateur ait été produit par le conteneur. La possibilité que deux parties du programme puissent modifier le même conteneur mène à un état incertain, l'exception notifie donc qu'il faut modifier le code - dans ce cas, récupérer l'itérateur après avoir ajouté tous les éléments au conteneur.

Notez qu'on ne peut bénéficier de ce genre de surveillance quand on accède aux éléments d'une List en utilisant get().

Ce livre a été écrit par Bruce Eckel ( télécharger la version anglaise : Thinking in java )
Ce chapitre a été traduit par Jérome Quelin ( groupe de traduction )
télécharger la version francaise (PDF) | Commandez le livre en version anglaise (amazon) | télécharger la version anglaise

pages : 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Penser en Java 2nde édition

Thinking in Java