 |
|
9) Stockage des objets |
|
|
|
|
| Texte original |
|
Traducteur :
Jérome Quelin |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Choosing between Maps
|
|
Choisir entre les Maps
|
|
|
|
When choosing between implementations of
Map, the size of the Map is what most
strongly affects performance, and the following test program gives an indication
of this trade-off:
|
|
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
// Demonstrates performance differences in 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;
// Or, choose the number of repetitions
// via the command line:
if(args.length > 0)
reps = Integer.parseInt(args[0]);
// Small:
test(new TreeMap(), 10, reps);
test(new HashMap(), 10, reps);
test(new Hashtable(), 10, reps);
// Medium:
test(new TreeMap(), 100, reps);
test(new HashMap(), 100, reps);
test(new Hashtable(), 100, reps);
// Large:
test(new TreeMap(), 1000, reps);
test(new HashMap(), 1000, reps);
test(new Hashtable(), 1000, reps);
}
} ///:~
|
|
//: 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);
}
} ///:~
|
|
|
|
Because the size of the map is the issue,
you’ll see that the timing tests divide the time by the size to normalize
each measurement. Here is one set of results. (Yours will probably be
different.)
|
|
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
|
|
|
| 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 |
|
|
|
|
As you might expect,
Hashtable performance is roughly equivalent to
HashMap. (You can also see that HashMap is generally a bit faster.
HashMap is intended to replace Hashtable.) The
TreeMap is generally slower than the
HashMap, so why would you use it? So you could use it not as a
Map, but as a way to create an ordered list. The behavior of a
tree is such that it’s always in order and doesn’t have to be
specially sorted. Once you fill a TreeMap, you can call
keySet( ) to get a Set view of the
keys, then toArray( ) to produce an array of
those keys. You can then use the static method
Arrays.binarySearch( ) (discussed later) to rapidly find objects in
your sorted array. Of course, you would probably only do this if, for some
reason, the behavior of a HashMap was unacceptable, since HashMap
is designed to rapidly find things. Also, you can easily create a HashMap
from a TreeMap with a single object creation In the end, when
you’re using a Map your first choice should be HashMap, and
only if you need a constantly sorted Map will you need
TreeMap.
|
|
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.
|
|
|
|
Sorting and searching
Lists
|
|
Trier et rechercher dans les Lists
|
|
|
|
Utilities to perform sorting and
searching for Lists have the same names and
signatures as those for sorting arrays of objects, but are static methods
of Collections instead of Arrays.
Here’s an example, modified from
ArraySearching.java:
|
|
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
// Sorting and searching Lists with '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));
}
} ///:~
|
|
//: 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));
}
} ///:~
|
|
|
|
The use of these methods is identical to
the ones in Arrays, but you’re using a List instead of an
array. Just like searching and sorting with arrays, if you sort using a
Comparator you must binarySearch( ) using the same
Comparator.
|
|
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().
|
|
|
|
This program also demonstrates the
shuffle( ) method in Collections,
which randomizes the order of a
List.
|
|
Ce programme illustre aussi la méthode shuffle() de
la classe Collections, qui modifie aléatoirement l'ordre d'une
List.
|
|
|
|
Utilities
|
|
Utilitaires
|
|
|
|
There are a number of other useful
utilities in the Collections class:
|
|
Il existe un certain nombre d'autres méthodes bien pratiques dans la classe
Collections :
|
|
|
|
enumeration(Collection)
|
Produces an old-style Enumeration
for the argument.
|
max(Collection)
min(Collection)
|
Produces the maximum or minimum element
in the argument using the natural comparison method of the objects in the
Collection.
|
max(Collection, Comparator)
min(Collection,
Comparator)
|
Produces the maximum or minimum element
in the Collection using the Comparator.
|
reverse( )
|
Reverses all the elements in
place.
|
copy(List dest, List
src)
|
Copies elements from src to
dest.
|
fill(List list, Object
o)
|
Replaces all the elements of list with
o.
|
nCopies(int n, Object o)
|
Returns an immutable List of size
n whose references all point to o.
|
|
|
| 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. |
|
|
|
|
Note that min( ) and
max( ) work with Collection objects, not with Lists,
so you don’t need to worry about whether the Collection should be
sorted or not. (As mentioned earlier, you do need to sort( )
a List or an array before performing a
binarySearch( ).)
|
|
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()).
|
|
|
|
Making a Collection or Map unmodifiable
|
|
Rendre une Collection ou une Map non-modifiable
|
|
|
|
Often it is convenient to create a
read-only version of a Collection or Map. The Collections
class allows you to do this by passing the original container into a method that
hands back a read-only version. There are four variations on this method, one
each for Collection (if you don’t want to treat a Collection
as a more specific type), List, Set, and Map. This
example shows the proper way to build read-only versions of
each:
|
|
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
// Using the Collections.unmodifiable methods.
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); // Insert data
c = Collections.unmodifiableCollection(c);
System.out.println(c); // Reading is OK
c.add("one"); // Can't change it
List a = new ArrayList();
Collections2.fill(a, gen.reset(), 25);
a = Collections.unmodifiableList(a);
ListIterator lit = a.listIterator();
System.out.println(lit.next()); // Reading OK
lit.add("one"); // Can't change it
Set s = new HashSet();
Collections2.fill(s, gen.reset(), 25);
s = Collections.unmodifiableSet(s);
System.out.println(s); // Reading OK
//! s.add("one"); // Can't change it
Map m = new HashMap();
Collections2.fill(m,
Collections2.geography, 25);
m = Collections.unmodifiableMap(m);
System.out.println(m); // Reading OK
//! m.put("Ralph", "Howdy!");
}
} ///:~
|
|
//: 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!");
}
} ///:~
|
|
|
|
In each case, you must fill the container
with meaningful data before you make it read-only. Once it is loaded, the
best approach is to replace the existing reference with the reference that is
produced by the “unmodifiable” call. That way, you don’t run
the risk of accidentally changing the contents once you’ve made it
unmodifiable. On the other hand, this tool also allows you to keep a modifiable
container as private within a class and to return a read-only reference
to that container from a method call. So you can change it from within the
class, but everyone else can only read it.
|
|
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.
|
|
|
|
Calling the “unmodifiable”
method for a particular type does not cause compile-time checking, but once the
transformation has occurred, any calls to methods that modify the contents of a
particular container will produce an
UnsupportedOperationException.
|
|
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.
|
|
|
|
Synchronizing a Collection or Map
|
|
Synchroniser une Collection ou une Map
|
|
|
|
The
synchronized keyword is an important part of the
subject of multithreading, a more complicated
topic that will not be introduced until Chapter 14. Here, I shall note only that
the Collections class contains a way to automatically synchronize an
entire container. The syntax is similar to the “unmodifiable”
methods:
|
|
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
// Using the Collections.synchronized methods.
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());
}
} ///:~
|
|
//: 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());
}
} ///:~
|
|
|
|
In this case, you immediately pass the
new container through the appropriate “synchronized” method; that
way there’s no chance of accidentally exposing the unsynchronized
version.
|
|
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.
|
|
|
|
Fail fast
|
|
Echec rapide
|
|
|
|
The Java containers also have a mechanism
to prevent more than one process from modifying the contents of a container. The
problem occurs if you’re iterating through a container and some other
process steps in and inserts, removes, or changes an object in that container.
Maybe you’ve already passed that object, maybe it’s ahead of you,
maybe the size of the container shrinks after you call
size( )—there are many scenarios for disaster. The Java
containers library incorporates a fail-fast mechanism that looks for any
changes to the container other than the ones your process is personally
responsible for. If it detects that someone else is modifying the container, it
immediately produces a ConcurrentModificationException. This is the
“fail-fast” aspect—it doesn’t try to detect a problem
later on using a more complex algorithm.
|
|
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.
|
|
|
|
It’s quite easy to see the
fail-fast mechanism in operation—all you have to do is create an iterator
and then add something to the collection that the iterator is pointing to, like
this:
|
|
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
// Demonstrates the "fail fast" behavior.
import java.util.*;
public class FailFast {
public static void main(String[] args) {
Collection c = new ArrayList();
Iterator it = c.iterator();
c.add("An object");
// Causes an exception:
String s = (String)it.next();
}
} ///:~
|
|
//: 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();
}
} ///:~
|
|
|
|
The exception happens because something
is placed in the container after the iterator is acquired from the
container. The possibility that two parts of the program could be modifying the
same container produces an uncertain state, so the exception notifies you that
you should change your code—in this case, acquire the iterator
after you have added all the elements to the container.
|
|
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.
|
|
|
|
Note that you cannot benefit from this
kind of monitoring when you’re accessing the elements of a List
using get( ).
|
|
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().
|
|
|
|
|
|
|
|
|
|
|
|
|
