Le moyen le plus efficace d'incrémenter une valeur Map en Java

Question

J'espère que cette question ne sera pas considérée comme trop basique pour ce forum, mais nous verrons bien. Je me demande comment refactoriser un code qui est exécuté plusieurs fois pour améliorer les performances.

Imaginons que je crée une liste de fréquence de mots, en utilisant une Map (probablement une HashMap), où chaque clé est une String avec le mot qui est compté et la valeur est un Integer qui est incrémenté chaque fois qu'un token du mot est trouvé.

En Perl, l'incrémentation d'une telle valeur serait trivialement facile :

$map{$word}++;

Mais en Java, c'est beaucoup plus compliqué. Voici la façon dont je le fais actuellement :

int count = map.containsKey(word) ? map.get(word) : 0;
map.put(word, count + 1);

Ce qui, bien sûr, repose sur la fonction de boîte automatique des nouvelles versions de Java. Je me demande si vous pouvez suggérer un moyen plus efficace d'incrémenter une telle valeur. Y a-t-il même de bonnes raisons, en termes de performances, d'éviter le framework Collections et d'utiliser quelque chose d'autre à la place ?

Mise à jour : J'ai fait un test de plusieurs des réponses. Voir ci-dessous.

Answer 1

Quelques résultats de tests

J'ai reçu beaucoup de bonnes réponses à cette question - merci à tous - et j'ai donc décidé de faire quelques tests pour déterminer la méthode la plus rapide. Les cinq méthodes que j'ai testées sont les suivantes :

• la méthode "ContainsKey" que j'ai présentée dans la question
• la méthode "TestForNull" suggérée par Aleksandar Dimitrov
• la méthode "AtomicLong" suggérée par Hank Gay
• la méthode "Trove" suggérée par jrudolph
• la méthode "MutableInt" proposée par phax.myopenid.com

Méthode

Voilà ce que j'ai fait...

1. a créé cinq classes identiques, à l'exception des différences indiquées ci-dessous. Chaque classe devait effectuer une opération typique du scénario que j'ai présenté : ouvrir un fichier de 10 Mo et le lire, puis effectuer un comptage de fréquence de tous les tokens de mots dans le fichier. Comme cette opération ne prenait en moyenne que 3 secondes, j'ai demandé à la classe d'effectuer le comptage de fréquence (et non les entrées/sorties) 10 fois.
2. a chronométré la boucle de 10 itérations mais pas l'opération I/O et a enregistré le temps total pris (en secondes d'horloge) en utilisant essentiellement La méthode de Ian Darwin dans le Java Cookbook .
3. a effectué les cinq tests en série, puis l'a refait trois fois.
4. a fait la moyenne des quatre résultats pour chaque méthode.

Résultats

Je vais présenter les résultats en premier et le code ci-dessous pour ceux qui sont intéressés.

El ContainsKey était, comme prévu, la plus lente, je vais donc donner la vitesse de chaque méthode par rapport à celle de cette dernière.

• ContainsKey : 30,654 secondes (ligne de base)
• AtomicLong : 29,780 secondes (1,03 fois plus rapide)
• TestForNull : 28,804 secondes (1,06 fois plus rapide)
• Trove : 26,313 secondes (1,16 fois plus rapide)
• MutableInt : 25,747 secondes (1,19 fois plus rapide)

Conclusions

Il semblerait que seules la méthode MutableInt et la méthode Trove soient significativement plus rapides, dans la mesure où elles sont les seules à offrir un gain de performance de plus de 10%. Cependant, si le threading est un problème, AtomicLong pourrait être plus intéressant que les autres (je ne suis pas vraiment sûr). J'ai également exécuté TestForNull avec final mais la différence est négligeable.

Notez que je n'ai pas établi de profil d'utilisation de la mémoire dans les différents scénarios. Je serais heureux d'entendre toute personne ayant une idée précise de la façon dont les méthodes MutableInt et Trove sont susceptibles d'affecter l'utilisation de la mémoire.

Personnellement, je trouve la méthode MutableInt la plus intéressante, car elle ne nécessite pas le chargement de classes tierces. Donc, à moins que je ne découvre des problèmes avec cette méthode, c'est celle que je choisirai le plus probablement.

Le code

Voici le code crucial de chaque méthode.

ContainsKey

import java.util.HashMap;
import java.util.Map;
...
Map<String, Integer> freq = new HashMap<String, Integer>();
...
int count = freq.containsKey(word) ? freq.get(word) : 0;
freq.put(word, count + 1);

TestForNull

import java.util.HashMap;
import java.util.Map;
...
Map<String, Integer> freq = new HashMap<String, Integer>();
...
Integer count = freq.get(word);
if (count == null) {
    freq.put(word, 1);
}
else {
    freq.put(word, count + 1);
}

AtomicLong

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.atomic.AtomicLong;
...
final ConcurrentMap<String, AtomicLong> map = 
    new ConcurrentHashMap<String, AtomicLong>();
...
map.putIfAbsent(word, new AtomicLong(0));
map.get(word).incrementAndGet();

Trove

import gnu.trove.TObjectIntHashMap;
...
TObjectIntHashMap<String> freq = new TObjectIntHashMap<String>();
...
freq.adjustOrPutValue(word, 1, 1);

MutableInt

import java.util.HashMap;
import java.util.Map;
...
class MutableInt {
  int value = 1; // note that we start at 1 since we're counting
  public void increment () { ++value;      }
  public int  get ()       { return value; }
}
...
Map<String, MutableInt> freq = new HashMap<String, MutableInt>();
...
MutableInt count = freq.get(word);
if (count == null) {
    freq.put(word, new MutableInt());
}
else {
    count.increment();
}

Answer 2

Pour faire suite à mon propre commentaire : Trove semble être la voie à suivre. Si, pour une raison ou une autre, vous voulez rester avec le JDK standard, ConcurrentMap y AtomicLong peut faire du code un petit un peu plus agréable, mais YMMV.

    final ConcurrentMap<String, AtomicLong> map = new ConcurrentHashMap<String, AtomicLong>();
    map.putIfAbsent("foo", new AtomicLong(0));
    map.get("foo").incrementAndGet();

laissera 1 comme valeur dans la carte pour foo . D'un point de vue réaliste, la convivialité accrue du threading est tout ce que cette approche a à recommander.

Answer 3

Google Goyave est votre ami...

...du moins dans certains cas. Ils ont cette belle AtomicLongMap . Particulièrement agréable parce que vous avez affaire à long comme valeur dans votre carte.

Par exemple

AtomicLongMap<String> map = AtomicLongMap.create();
[...]
map.getAndIncrement(word);

Il est également possible d'ajouter plus de 1 à la valeur :

map.getAndAdd(word, 112L);

Answer 4

C'est toujours une bonne idée de regarder le Bibliothèque Google Collections pour ce genre de choses. Dans ce cas, un Multiset fera l'affaire :

Multiset bag = Multisets.newHashMultiset();
String word = "foo";
bag.add(word);
bag.add(word);
System.out.println(bag.count(word)); // Prints 2

Il existe des méthodes de type Map pour itérer sur les clés/entrées, etc. En interne, l'implémentation utilise actuellement un HashMap<E, AtomicInteger> Vous n'aurez donc pas à payer de frais de boxe.

Answer 5

Vous devez être conscient du fait que votre tentative initiale

int count = map.containsKey(word) ? map.get(word) : 0;

contient deux opérations potentiellement coûteuses sur une carte, à savoir containsKey y get . Le premier effectue une opération potentiellement très similaire au second, donc vous faites le même travail. deux fois !

Si vous regardez l'API pour Map, get Les opérations retournent généralement null lorsque la carte ne contient pas l'élément demandé.

Notez que cela rendra une solution comme

map.put( key, map.get(key) + 1 );

dangereux, car il pourrait donner NullPointerException s. Vous devez vérifier si un null d'abord.

Notez également et c'est très important, que HashMap s peut contiennent nulls par définition. Donc, tous les retours null dit "cet élément n'existe pas". À cet égard, containsKey se comporte comme suit : différemment de get en vous disant réellement si il existe un tel élément. Reportez-vous à l'API pour plus de détails.

Dans votre cas, cependant, vous ne voudrez peut-être pas faire la distinction entre un fichier stocké null et "noSuchElement". Si vous ne voulez pas autoriser null vous pourriez préférer un Hashtable . L'utilisation d'une bibliothèque wrapper comme cela a déjà été proposé dans d'autres réponses pourrait être une meilleure solution que le traitement manuel, selon la complexité de votre application.

Pour compléter la réponse (et j'ai oublié de le mettre au début, grâce à la fonction d'édition !), la meilleure façon de le faire en mode natif est de get en un final vérifiez la présence de la variable null y put avec un 1 . La variable doit être final parce que c'est immuable de toute façon. Le compilateur n'a peut-être pas besoin de cette indication, mais c'est plus clair comme ça.

final HashMap map = generateRandomHashMap();
final Object key = fetchSomeKey();
final Integer i = map.get(key);
if (i != null) {
    map.put(i + 1);
} else {
    // do something
}

Si vous ne voulez pas compter sur l'autoboxage, vous devriez dire quelque chose comme map.put(new Integer(1 + i.getValue())); à la place.