Chapitre 9 - Stockage des objets

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

Notez que PrintData.print() s'appuie sur le fait que les objets dans les conteneurs appartiennent à la classe Object et donc l'appel à toString() par System.out.println() est automatique. Il est toutefois plus courant de devoir assumer qu'un Iterator parcourt un conteneur d'un type spécifique. Par exemple, on peut assumer que tous les objets d'un conteneur sont une Shape possédant une méthode draw(). On doit alors effectuer un transtypage descendant depuis l'Object renvoyé par Iterator.next() pour produire une Shape.

Choisir une implémentation

Vous devriez maintenant être conscient qu'il n'existe que trois types de conteneurs : les Maps, les Lists et les Sets, avec seulement deux ou trois implémentations pour chacune de ces interfaces. Mais si on décide d'utiliser les fonctionnalités offertes par une interface particulière, comment choisir l'implémentation qui conviendra le mieux ?

Il faut bien voir que chaque implémentation dispose de ses propres fonctionnalités, forces et faiblesses. Par exemple, on peut voir dans le diagramme que les classes Hashtable, Vector et Stack sont des reliquats des versions précédentes de Java, ce vieux code testé et retesté n'est donc pas près d'être pris en défaut. D'un autre côté, il vaut mieux utiliser du code Java 2.

La distinction entre les autres conteneurs se ramène la plupart du temps à leur « support sous-jacent » ; c'est à dire la structure de données qui implémente physiquement l'interface désirée. Par exemple, les ArrayLists et les LinkedLists implémentent toutes les deux l'interface List, donc un programme produira les mêmes résultats quelle que soit celle qui est choisie. Cependant, une ArrayList est sous-tendue par un tableau, tandis qu'une LinkedList est implémentée sous la forme d'une liste doublement chaînée, dont chaque objet individuel contient des données ainsi que des références sur les éléments précédents et suivants dans la liste. De ce fait, une LinkedList est le choix approprié si on souhaite effectuer de nombreuses insertions et suppressions au milieu de la liste (les LinkedLists proposent aussi des fonctionnalités supplémentaires précisées dans AbstractSequentialList). Dans les autres cas, une ArrayList est typiquement plus rapide.

De même, un Set peut être implémenté soit sous la forme d'un TreeSet ou d'un HashSet. Un TreeSet est supporté par un TreeMap et est conçu pour produire un Set constamment trié. Cependant, si le Set est destiné à stocker de grandes quantités d'objets, les performances en insertion du TreeSet vont se dégrader. Quand vous écrirez un programme nécessitant un Set, choisissez un HashSet par défaut, et changez pour un TreeSet s'il est plus important de disposer d'un Set constamment trié.

Choisir entre les Lists

Un test de performances constitue la façon la plus flagrante de voir les différences entre les implémentations des Lists. Le code suivant crée une classe interne de base à utiliser comme structure de test, puis crée un tableau de classes internes anonymes, une pour chaque test différent. Chacune de ces classes internes est appelée par la méthode test(). Cette approche permet d'ajouter et de supprimer facilement de nouveaux tests.

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

public class ListPerformance {
  private abstract static class Tester {
    String name;
    int size; // Nombre de tests par répétition
    Tester(String name, int size) {
      this.name = name;
      this.size = size;
    }
    abstract void test(List a, int reps);
  }
  private static Tester[] tests = {
    new Tester("get", 300) {
      void test(List a, int reps) {
        for(int i = 0; i < reps; i++) {
          for(int j = 0; j < a.size(); j++)
            a.get(j);
        }
      }
    },
    new Tester("iteration", 300) {
      void test(List a, int reps) {
        for(int i = 0; i < reps; i++) {
          Iterator it = a.iterator();
          while(it.hasNext())
            it.next();
        }
      }
    },
    new Tester("insert", 5000) {
      void test(List a, int reps) {
        int half = a.size()/2;
        String s = "test";
        ListIterator it = a.listIterator(half);
        for(int i = 0; i < size * 10; i++)
          it.add(s);
      }
    },
    new Tester("remove", 5000) {
      void test(List a, int reps) {
        ListIterator it = a.listIterator(3);
        while(it.hasNext()) {
          it.next();
          it.remove();
        }
      }
    },
  };
  public static void test(List a, int reps) {
    // Une astuce pour imprimer le nom de la classe :
    System.out.println("Testing " +
      a.getClass().getName());
    for(int i = 0; i < tests.length; i++) {
      Collections2.fill(a,
        Collections2.countries.reset(),
        tests[i].size);
      System.out.print(tests[i].name);
      long t1 = System.currentTimeMillis();
      tests[i].test(a, reps);
      long t2 = System.currentTimeMillis();
      System.out.println(": " + (t2 - t1));
    }
  }
  public static void testArray(int reps) {
    System.out.println("Testing array as List");
    // On ne peut effectuer que les deux premiers tests sur un tableau :
    for(int i = 0; i < 2; i++) {
      String[] sa = new String[tests[i].size];
      Arrays2.fill(sa,
        Collections2.countries.reset());
      List a = Arrays.asList(sa);
      System.out.print(tests[i].name);
      long t1 = System.currentTimeMillis();
      tests[i].test(a, reps);
      long t2 = System.currentTimeMillis();
      System.out.println(": " + (t2 - t1));
    }
  }
  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]);
    System.out.println(reps + " repetitions");
    testArray(reps);
    test(new ArrayList(), reps);
    test(new LinkedList(), reps);
    test(new Vector(), reps);
  }
} ///:~

La classe interne Tester est abstract, pour fournir une classe de base aux tests spécifiques. Elle contient une String à imprimer quand le test débute, un paramètre size destiné à être utilisé par le test comme quantité d'éléments ou nombre de répétitions des tests, un constructeur pour initialiser les champs et un méthode abstract test() qui réalise le travail. Tous les types de tests sont regroupés dans le tableau tests, initialisé par différentes classes internes anonymes dérivées de Tester. Pour ajouter ou supprimer des tests, il suffit d'ajouter ou de supprimer la définition d'une classe interne dans le tableau, et le reste est géré automatiquement.

Pour comparer l'accès aux tableaux avec l'accès aux conteneurs (et particulièrement avec les ArrayLists), un test spécial est créé pour les tableaux en en encapsulant un dans une List via Arrays.asList(). Notez que seuls les deux premiers tests peuvent être réalisés dans ce cas, parce qu'on ne peut insérer ou supprimer des éléments dans un tableau.

La List passée à test() est d'abord remplie avec des éléments, puis chaque test du tableau tests est chronométré. Les résultats dépendent bien entendu de la machine ; ils sont seulement conçus pour donner un ordre de comparaison entre les performances des différents conteneurs. Voici un résumé pour une exécution :

Type	Get	Iteration	Insert	Remove
tableau	1430	3850	na	na
ArrayList	3070	12200	500	46850
LinkedList	16320	9110	110	60
Vector	4890	16250	550	46850

Comme prévu, les tableaux sont plus rapides que n'importe quel conteneur pour les accès aléatoires et les itérations. On peut voir que les accès aléatoires (get()) sont bon marché pour les ArrayLists et coûteux pour les LinkedLists (bizarrement, l'itération est plus rapide pour une LinkedList que pour une ArrayList, ce qui est quelque peu contre-intuitif). D'un autre côté, les insertions et les suppressions au milieu d'une liste sont spectaculairement meilleur marché pour une LinkedList que pour une ArrayList - et particulièrement les suppressions. Les Vectors ne sont pas aussi rapides que les ArrayLists, et doivent être évités ; ils ne sont présents dans la bibliothèque que pour fournir une compatibilité ascendante avec le code existant (la seule raison pour laquelle ils fonctionnent dans ce programme est qu'ils ont été adaptés pour être une List dans Java 2). La meilleure approche est de choisir une ArrayList par défaut, et de changer pour une LinkedList si on découvre des problèmes de performance dûs à de nombreuses insertions et suppressions au milieu de la liste. Bien sûr, si on utilise un ensemble d'éléments de taille fixée, il faut se tourner vers un tableau.

Choisir entre les Sets

Suivant la taille du Set, on peut se tourner vers un TreeSet ou un HashSet (si on a besoin de produire une séquence ordonnée à partir d'un Set, il faudra utiliser un TreeSet). Le programme de test suivant donne une indication de ce compromis :

//: c09:SetPerformance.java
import java.util.*;
import com.bruceeckel.util.*;

public class SetPerformance {
  private abstract static class Tester {
    String name;
    Tester(String name) { this.name = name; }
    abstract void test(Set s, int size, int reps);
  }
  private static Tester[] tests = {
    new Tester("add") {
      void test(Set s, int size, int reps) {
        for(int i = 0; i < reps; i++) {
          s.clear();
          Collections2.fill(s,
            Collections2.countries.reset(),size);
        }
      }
    },
    new Tester("contains") {
      void test(Set s, int size, int reps) {
        for(int i = 0; i < reps; i++)
          for(int j = 0; j < size; j++)
            s.contains(Integer.toString(j));
      }
    },
    new Tester("iteration") {
      void test(Set s, int size, int reps) {
        for(int i = 0; i < reps * 10; i++) {
          Iterator it = s.iterator();
          while(it.hasNext())
            it.next();
        }
      }
    },
  };
  public static void
  test(Set s, int size, int reps) {
    System.out.println("Testing " +
      s.getClass().getName() + " size " + size);
    Collections2.fill(s,
      Collections2.countries.reset(), size);
    for(int i = 0; i < tests.length; i++) {
      System.out.print(tests[i].name);
      long t1 = System.currentTimeMillis();
      tests[i].test(s, 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 TreeSet(), 10, reps);
    test(new HashSet(), 10, reps);
    // Moyen :
    test(new TreeSet(), 100, reps);
    test(new HashSet(), 100, reps);
    // Gros :
    test(new TreeSet(), 1000, reps);
    test(new HashSet(), 1000, reps);
  }
} ///:~

Le tableau suivant montre les résultats d'une exécution (bien sûr, vous obtiendrez des valeurs différentes suivant votre ordinateur et la JVM que vous utilisez ; lancez les tests vous-même pour vous faire une idée) :

Type	Test size	Add	Contains	Iteration
	10	138.0	115.0	187.0
TreeSet	100	189.5	151.1	206.5
	1000	150.6	177.4	40.04
	10	55.0	82.0	192.0
HashSet	100	45.6	90.0	202.2
	1000	36.14	106.5	39.39

Les performances d'un HashSet sont généralement supérieures à celles d'un TreeSet pour toutes les opérations (et en particulier le stockage et la recherche, les deux opérations les plus fréquentes). La seule raison d'être du TreeSet est qu'il maintient ses éléments triés, on ne l'utilisera donc que lorsqu'on aura besoin d'un Set trié.

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