 |
|
|
9) Stockage des objets |
|
|
|
|
| Texte original |
|
Traducteur : Jérome QUELIN |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
For the HashMap, the
entrySet( ) method produces a Set of Map.entry
objects, which contain both the key and the value for each entry, so you see
both of them printed.
|
|
Pour le HashMap, la méthode entrySet()
renvoie un Set d'objets Map.entry, qui contient à la fois la clef
et la valeur pour chaque entrée, afin d'afficher les deux.
|
|
|
|
|
Note that PrintData.print( )
takes advantage of the fact that the objects in these containers are of class
Object so the call toString( ) by
System.out.println( ) is automatic. It’s more likely that in
your problem, you must make the assumption that your Iterator is walking
through a container of some specific type. For example, you might assume that
everything in the container is a Shape with a draw( ) method.
Then you must downcast from the Object that Iterator.next( )
returns to produce a Shape.
|
|
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.
|
|
|
|
Choosing an implementation
|
|
Choisir une implémentation
|
|
|
|
|
By now you should understand that there
are really only three container components: Map, List, and
Set, and only two or three implementations of each interface. If you need
to use the functionality offered by a particular interface, how do you
decide which particular implementation to use?
|
|
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 ?
|
|
|
|
|
To understand the answer, you must be
aware that each different implementation has its own features, strengths, and
weaknesses. For example, you can see in the diagram that the
“feature” of Hashtable, Vector, and Stack is
that they are legacy classes, so that old code doesn’t break. On the other
hand, it’s best if you don’t use those for new (Java 2)
code.
|
|
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.
|
|
|
|
|
The distinction between the other
containers often comes down to what they are “backed by”; that is,
the data structures that physically implement your desired interface.
This means that, for example, ArrayList and LinkedList implement
the List interface so your program will produce the same results
regardless of the one you use. However, ArrayList is backed by an array,
while the LinkedList is implemented in the usual way for a doubly linked
list, as individual objects each containing data along with references to the
previous and next elements in the list. Because of this, if you want to do many
insertions and removals in the middle of a list, a LinkedList is the
appropriate choice. (LinkedList also has additional functionality that is
established in AbstractSequentialList.) If not,
an ArrayList is typically faster.
|
|
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.
|
|
|
|
|
As another example, a Set can be
implemented as either a TreeSet or a HashSet. A TreeSet is
backed by a TreeMap and is designed to produce a constantly sorted set.
However, if you’re going to have larger quantities in your Set, the
performance of TreeSet insertions will get slow. When you’re
writing a program that needs a Set, you should choose HashSet by
default, and change to TreeSet when it's more important to have a
constantly sorted set.
|
|
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é.
|
|
|
|
Choosing between Lists
|
|
Choisir entre les Lists
|
|
|
|
|
The most convincing way to see the
differences between the implementations of List is with a performance
test. The following code establishes an inner base class to use as a test
framework, then creates an array of
anonymous
inner classes, one for each different test. Each of these inner classes is
called by the test( ) method. This approach allows you to easily add
and remove new kinds of tests.
|
|
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
// Demonstrates performance differences in Lists.
import java.util.*;
import com.bruceeckel.util.*;
public class ListPerformance {
private abstract static class Tester {
String name;
int size; // Test quantity
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) {
// A trick to print out the class name:
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");
// Can only do first two tests on an array:
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;
// Or, choose the number of repetitions
// via the command line:
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);
}
} ///:~
|
|
//: 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);
}
} ///:~
|
|
|
|
|
The inner class Tester is
abstract, to provide a base class for the specific tests. It contains a
String to be printed when the test starts, a size parameter to be
used by the test for quantity of elements or repetitions of tests, a constructor
to initialize the fields, and an abstract method test( ) that
does the work. All the different types of tests are collected in one place, the
array tests, which is initialized with different anonymous inner classes
that inherit from Tester. To add or remove tests, simply add or remove an
inner class definition from the array, and everything else happens
automatically.
|
|
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.
|
|
|
|
|
To compare array access to container
access (primarily against ArrayList), a special test is created for
arrays by wrapping one as a List using Arrays.asList( ). Note
that only the first two tests can be performed in this case, because you cannot
insert or remove elements from an array.
|
|
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.
|
|
|
|
|
The List that’s handed to
test( ) is first filled with elements, then each test in the
tests array is timed. The results will vary from machine to machine; they
are intended to give only an order of magnitude comparison between the
performance of the different containers. Here is a summary of one
run:
|
|
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
|
|
array
|
1430
|
3850
|
na
|
na
|
|
ArrayList
|
3070
|
12200
|
500
|
46850
|
|
LinkedList
|
16320
|
9110
|
110
|
60
|
|
Vector
|
4890
|
16250
|
550
|
46850
|
|
|
| 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 |
|
|
|
|
|
As expected, arrays are faster than any
container for random-access lookups and iteration. You can see that random
accesses (get( )) are cheap for ArrayLists and expensive for
LinkedLists. (Oddly, iteration is faster for a
LinkedList than an
ArrayList, which is a bit counterintuitive.) On
the other hand, insertions and removals from the middle of a list are
dramatically cheaper for a LinkedList than for an
ArrayList—especially removals.
Vector is generally not as fast as
ArrayList, and it should be avoided; it’s only in the library for
legacy code support (the only reason it works in this program is because it was
adapted to be a List in Java 2). The best approach is probably to
choose an ArrayList as your default, and to change to a LinkedList
if you discover performance problems due to many insertions and removals from
the middle of the list. And of course, if you are working with a fixed-sized
group of elements, use an array.
|
|
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.
|
|
|
|
Choosing between Sets
|
|
Choisir entre les Sets
|
|
|
|
|
You can choose between a
TreeSet and a
HashSet, depending on the size of the
Set (if you need to produce an ordered sequence
from a Set, use TreeSet). The following test program gives
an indication of this trade-off:
|
|
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;
// Or, choose the number of repetitions
// via the command line:
if(args.length > 0)
reps = Integer.parseInt(args[0]);
// Small:
test(new TreeSet(), 10, reps);
test(new HashSet(), 10, reps);
// Medium:
test(new TreeSet(), 100, reps);
test(new HashSet(), 100, reps);
// Large:
test(new TreeSet(), 1000, reps);
test(new HashSet(), 1000, reps);
}
} ///:~
|
|
//: 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);
}
} ///:~
|
|
|
|
|
The following table shows the results of
one run. (Of course, this will be different according to the computer and JVM
you are using; you should run the test yourself as well):
|
|
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
|
|
|
| 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 |
|
|
|
|
|
The performance of HashSet is
generally superior to TreeSet for all operations (but in particular
addition and lookup, the two most important operations). The only reason
TreeSet exists is because it maintains its elements in sorted order, so
you only use it when you need a sorted
Set.
|
|
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é.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
 |
