Le moyen le plus efficace pour incrémenter une valeur de carte en Java

J’espère que cette question n’est pas considérée comme trop fondamentale pour ce forum, mais nous verrons. Je me demande comment réorganiser du code pour obtenir de meilleures performances.

Supposons que je crée une liste de fréquences de mots, en utilisant une carte (probablement une HashMap), où chaque clé est une chaîne avec le mot qui est compté et la valeur est un entier qui est incrémenté chaque fois qu’un mot du mot est trouvé.

En Perl, l’incrémentation d’une telle valeur serait très simple:

$map{$word}++; 

Mais en Java, c’est beaucoup plus compliqué. Voici comment je le fais actuellement:

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

Ce qui dépend bien sûr de la fonctionnalité de création automatique de boîtes aux lettres dans les nouvelles versions de Java. Je me demande si vous pouvez suggérer un moyen plus efficace d’incrémenter une telle valeur. Existe-t-il même de bonnes raisons d’abandonner le cadre des Collections et d’utiliser un autre élément à la place?

Mise à jour: J’ai testé plusieurs des réponses. Voir ci-dessous.

Quelques résultats de test

J’ai eu beaucoup de bonnes réponses à cette question – merci les gens – j’ai donc décidé de faire des tests et de trouver 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” proposée par Aleksandar Dimitrov
  • la méthode “AtomicLong” proposée par Hank Gay
  • la méthode “Trove” proposée par jrudolph
  • la méthode “MutableInt” proposée par phax.myopenid.com

Méthode

Voici ce que j’ai fait …

  1. créé cinq classes identiques sauf les différences indiquées ci-dessous. Chaque classe devait effectuer une opération typique du scénario que je présentais: ouvrir un fichier de 10 Mo et le lire, puis effectuer un comptage de fréquence de tous les jetons de mot du fichier. Comme cela ne prenait en moyenne que 3 secondes, je lui ai demandé d’effectuer le comptage de fréquence (pas les entrées / sorties) 10 fois.
  2. chronométré la boucle de 10 itérations mais pas l’opération d’E / S et enregistré le temps total pris (en secondes) en utilisant essentiellement la méthode de Ian Darwin dans le Java Cookbook .
  3. effectué les cinq tests en série, puis fait cela trois autres fois.
  4. en moyenne les quatre résultats pour chaque méthode.

Résultats

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

Comme prévu, la méthode ContainsKey était la plus lente. Je vais donc donner la vitesse de chaque méthode par rapport à la vitesse de cette méthode.

  • ContainsKey: 30.654 secondes (baseline)
  • 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 vite)
  • 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ù seules ces dernières augmentent les performances de plus de 10%. Cependant, si le threading est un problème, AtomicLong pourrait être plus attrayant que les autres (je ne suis pas vraiment sûr). J’ai également exécuté TestForNull avec les variables final , mais la différence était négligeable.

Notez que je n’ai pas profilé l’utilisation de la mémoire dans les différents scénarios. Je serais ravi de recevoir des informations sur la manière dont les méthodes MutableInt et Trove pourraient affecter l’utilisation de la mémoire.

Personnellement, je trouve la méthode MutableInt la plus attrayante, car elle ne nécessite aucun chargement de classes tierces. Donc, à moins que je découvre des problèmes, c’est ce que je suis le plus susceptible de faire.

Le code

Voici le code crucial de chaque méthode.

ContainsKey

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

TestForNull

 import java.util.HashMap; import java.util.Map; ... Map freq = new HashMap(); ... 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 map = new ConcurrentHashMap(); ... map.putIfAbsent(word, new AtomicLong(0)); map.get(word).incrementAndGet(); 

Trove

 import gnu.trove.TObjectIntHashMap; ... TObjectIntHashMap freq = new TObjectIntHashMap(); ... 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 freq = new HashMap(); ... MutableInt count = freq.get(word); if (count == null) { freq.put(word, new MutableInt()); } else { count.increment(); } 

OK, peut-être une vieille question, mais il existe un moyen plus court avec Java 8:

 Map.merge(key, 1, Integer::sum) 

Ce qu’il fait: si la clé n’existe pas, mettez 1 comme valeur, sinon additionnez 1 à la valeur liée à la clé . Plus d’informations ici

Une petite recherche en 2016: https://github.com/leventov/java-word-count , code source de référence

Meilleurs résultats par méthode (moins c’est mieux):

  time, ms kolobokeComstack 18.8 koloboke 19.8 trove 20.8 fastutil 22.7 mutableInt 24.3 atomicInteger 25.3 eclipse 26.9 hashMap 28.0 hppc 33.6 hppcRt 36.5 

Temps \ résultats d’espace:

@Hank Gay

Pour faire suite à mon commentaire (plutôt inutile): Trove semble être la voie à suivre. Si, pour quelque raison que ce soit, vous souhaitiez conserver le JDK standard, ConcurrentMap et AtomicLong peuvent rendre le code un peu plus agréable, même si YMMV.

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

laissera 1 comme valeur dans la carte pour foo . De manière réaliste, la convivialité accrue au filetage est tout ce que cette approche doit recommander.

Google Guava est votre ami …

… au moins dans certains cas. Ils ont cette belle AtomicLongMap . Particulièrement bien parce que vous traitez avec long comme valeur dans votre carte.

Par exemple

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

Aussi possible d’append plus de 1 à la valeur:

 map.getAndAdd(word, new Long(112)); 

C’est toujours une bonne idée de regarder la bibliothèque de collections Google pour ce genre de chose. Dans ce cas, un Multiset fera l’affaire:

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

Il existe des méthodes de type carte pour effectuer une itération sur les clés / entrées, etc. En interne, l’implémentation utilise actuellement une HashMap , de sorte que vous ne subirez pas de frais de boxe.

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 et get . Le premier effectue une opération potentiellement très similaire à la seconde, vous faites donc le même travail deux fois !

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

Notez que cela fera une solution comme

  map.put (clé, map.get (clé) + 1); 

dangereux, car il pourrait donner NullPointerException s. Vous devez d’abord vérifier la valeur null .

Notez également , et c’est très important, que HashMap peut contenir des HashMap par définition. Donc, tous les null renvoyés ne disent pas “il n’y a pas un tel élément”. À cet égard, containsKey se comporte différemment de get in réellement vous dire s’il existe un tel élément. Reportez-vous à l’API pour plus de détails.

Pour votre cas, cependant, vous ne voudrez peut-être pas faire la distinction entre un null stocké et “noSuchElement”. Si vous ne voulez pas autoriser null vous préférerez peut-être une Hashtable . Utiliser une bibliothèque de wrappers comme cela a déjà été proposé dans d’autres réponses pourrait être une meilleure solution pour le traitement manuel, en fonction de la complexité de votre application.

Pour compléter la réponse (et j’ai oublié de la mettre au départ, grâce à la fonction d’édition!), La meilleure façon de le faire en natif est d’ get dans une variable final , de vérifier la valeur null et de la put avec un 1 . La variable devrait être final car elle est immuable de toute façon. Le compilateur n’a peut-être pas besoin de cet indice, mais c’est plus clair.

 HashMap final map = generateRandomHashMap ();
 clé d'object finale = fetchSomeKey ();
 Entier final i = map.get (clé);
 si (i! = null) {
     map.put (i + 1);
 } autre {
     // faire quelque chose
 }

Si vous ne voulez pas vous fier à la création automatique, vous devriez dire quelque chose comme map.put(new Integer(1 + i.getValue())); au lieu.

Une autre façon serait de créer un entier mutable:

 class MutableInt { int value = 0; public void inc () { ++value; } public int get () { return value; } } ... Map map = new HashMap (); MutableInt value = map.get (key); if (value == null) { value = new MutableInt (); map.put (key, value); } else { value.inc (); } 

Bien sûr, cela implique de créer un object supplémentaire, mais la surcharge par rapport à la création d’un entier (même avec Integer.valueOf) ne devrait pas être trop grande.

 Map map = new HashMap<>(); String key = "a random key"; int count = map.getOrDefault(key, 0); map.put(key, count + 1); 

Et c’est ainsi que vous incrémentez une valeur avec du code simple.

Avantage:

  • Ne pas créer une autre classe pour int modifiable
  • Petit code
  • Facile à comprendre
  • Aucune exception de pointeur nul

Une autre méthode consiste à utiliser la méthode de fusion, mais c’est trop pour simplement incrémenter une valeur.

 map.merge(key, 1, (a,b) -> a+b); 

Suggestion: vous devriez vous soucier de la lisibilité du code plus que peu de gain de performance dans la plupart des cas.

La rotation de la mémoire peut être un problème ici, puisque chaque boxing d’un int supérieur ou égal à 128 provoque une allocation d’object (voir Integer.valueOf (int)). Bien que le ramasse-miettes traite très efficacement les objects de courte durée, les performances en souffriront dans une certaine mesure.

Si vous savez que le nombre d’incréments effectués dépassera largement le nombre de clés (= mots dans ce cas), envisagez plutôt d’utiliser un titulaire int. Phax a déjà présenté du code pour cela. La voici à nouveau, avec deux modifications (la classe de titulaire a rendu la valeur statique et la valeur initiale définie sur 1):

 static class MutableInt { int value = 1; void inc() { ++value; } int get() { return value; } } ... Map map = new HashMap(); MutableInt value = map.get(key); if (value == null) { value = new MutableInt(); map.put(key, value); } else { value.inc(); } 

Si vous avez besoin de performances extrêmes, recherchez une implémentation Map directement adaptée aux types de valeurs primitifs. jrudolph a mentionné GNU Trove .

Par ailleurs, un bon terme de recherche pour ce sujet est “histogramme”.

Au lieu d’appeler containsKey (), il est plus rapide d’appeler map.get et de vérifier si la valeur renvoyée est nulle ou non.

  Integer count = map.get(word); if(count == null){ count = 0; } map.put(word, count + 1); 

Vous pouvez utiliser la méthode computeIfAbsent dans l’interface de Map fournie avec Java 8 .

 final Map map = new ConcurrentHashMap<>(); map.computeIfAbsent("A", k->new AtomicLong(0)).incrementAndGet(); map.computeIfAbsent("B", k->new AtomicLong(0)).incrementAndGet(); map.computeIfAbsent("A", k->new AtomicLong(0)).incrementAndGet(); //[A=2, B=1] 

La méthode computeIfAbsent vérifie si la clé spécifiée est déjà associée à une valeur ou non? S’il n’y a pas de valeur associée, il tente de calculer sa valeur en utilisant la fonction de mappage donnée. Dans tous les cas, il renvoie la valeur actuelle (existante ou calculée) associée à la clé spécifiée, ou null si la valeur calculée est nulle.

Si vous avez une situation où plusieurs threads mettent à jour une sum commune, vous pouvez regarder la classe LongAdder. En cas de forte contention, le débit attendu de cette classe est nettement supérieur à AtomicLong , au désortingment de la consommation d’espace.

Etes-vous sûr que c’est un goulot d’étranglement? Avez-vous effectué une parsing de performance?

Essayez d’utiliser le profileur NetBeans (gratuit et intégré à NB 6.1) pour examiner les zones sensibles.

Enfin, une mise à niveau de la JVM (disons de 1,5 à 1,6) est souvent un booster de performances bon marché. Même une mise à niveau du numéro de version peut fournir de bons gains de performances. Si vous utilisez Windows et qu’il s’agit d’une application de classe serveur, utilisez -server sur la ligne de commande pour utiliser la machine virtuelle Java Hotspot du serveur. Sur les machines Linux et Solaris, celle-ci est détectée automatiquement.

Il y a quelques approches:

  1. Utilisez un alorithme Bag comme les ensembles contenus dans Google Collections.

  2. Créez un conteneur modifiable que vous pouvez utiliser dans la carte:

class My{ Ssortingng word; int count; }
class My{ Ssortingng word; int count; } 

Et utilisez put (“word”, new My (“Word”)); Ensuite, vous pouvez vérifier s’il existe et l’incrémenter lors de l’ajout.

Évitez de déployer votre propre solution à l’aide de listes, car si vous effectuez une recherche et un sorting sur le canal interne, vos performances seront mauvaises. La première solution HashMap est en fait assez rapide, mais une version similaire à celle de Google Collections est probablement meilleure.

Compter les mots en utilisant Google Collections ressemble à ceci:

HashMultiset s = new HashMultiset(); s.add("word"); s.add("word"); System.out.println(""+s.count("word") );
HashMultiset s = new HashMultiset(); s.add("word"); s.add("word"); System.out.println(""+s.count("word") ); 

L’utilisation du HashMultiset est assez élégante, car un algorithme de type bag est exactement ce dont vous avez besoin pour compter des mots.

Je pense que votre solution serait la solution standard, mais – comme vous l’avez noté vous-même – ce n’est probablement pas le moyen le plus rapide possible.

Vous pouvez regarder GNU Trove . C’est une bibliothèque qui contient toutes sortes de collections primitives rapides. Votre exemple utiliserait un TObjectIntHashMap qui a une méthode adjustOrPutValue qui fait exactement ce que vous voulez.

Une variante de l’approche de MutableInt qui pourrait être encore plus rapide, si un peu un hack, consiste à utiliser un tableau à élément unique:

 Map map = new HashMap(); ... int[] value = map.get(key); if (value == null) map.put(key, new int[]{1} ); else ++value[0]; 

Il serait intéressant que vous puissiez relancer vos tests de performance avec cette variante. Ce pourrait être le plus rapide.


Edit: Le modèle ci-dessus a bien fonctionné pour moi, mais j’ai finalement changé pour utiliser les collections de Trove afin de réduire la taille de la mémoire dans certaines cartes très volumineuses que je créais – et en bonus, c’était aussi plus rapide.

Une fonctionnalité vraiment intéressante est que la classe TObjectIntHashMap possède un seul appel adjustOrPutValue qui, selon qu’il existe déjà une valeur pour cette clé, va mettre une valeur initiale ou incrémenter la valeur existante. Ceci est parfait pour l’incrémentation:

 TObjectIntHashMap map = new TObjectIntHashMap(); ... map.adjustOrPutValue(key, 1, 1); 

Google Collections HashMultiset:
– assez élégant à utiliser
– mais consumr CPU et mémoire

Le mieux serait d’avoir une méthode comme: Entry getOrPut(K); (élégant et peu coûteux)

Une telle méthode ne calculera qu’une seule fois le hash et l’index, puis nous pourrons faire ce que nous voulons avec l’entrée (remplacer ou mettre à jour la valeur).

Plus élégant:
– prendre un HashSet
– étendre le pour que get(K) mette une nouvelle entrée si nécessaire
– L’entrée pourrait être votre propre object.
-> (new MyHashSet()).get(k).increment();

“mettre” a besoin de “obtenir” (pour assurer aucune clé en double).
Alors, faites directement un “put”,
et s’il y avait une valeur précédente, faites un ajout:

 Map map = new HashMap (); MutableInt newValue = new MutableInt (1); // default = inc MutableInt oldValue = map.put (key, newValue); if (oldValue != null) { newValue.add(oldValue); // old + inc } 

Si count commence à 0, ajoutez 1: (ou toute autre valeur …)

 Map map = new HashMap (); MutableInt newValue = new MutableInt (0); // default MutableInt oldValue = map.put (key, newValue); if (oldValue != null) { newValue.setValue(oldValue + 1); // old + inc } 

Remarque: Ce code n’est pas thread-safe. Utilisez-le pour construire, puis utilisez la carte pour ne pas la mettre à jour simultanément.

Optimisation: dans une boucle, conservez l’ancienne valeur pour qu’elle devienne la nouvelle valeur de la prochaine boucle.

 Map map = new HashMap (); final int defaut = 0; final int inc = 1; MutableInt oldValue = new MutableInt (default); while(true) { MutableInt newValue = oldValue; oldValue = map.put (key, newValue); // insert or... if (oldValue != null) { newValue.setValue(oldValue + inc); // ...update oldValue.setValue(default); // reuse } else oldValue = new MutableInt (default); // renew } } 

Les différents wrappers primitifs, par exemple Integer sont immuables, donc il n’y a pas vraiment de moyen plus concis de faire ce que vous demandez à moins de pouvoir le faire avec quelque chose comme AtomicLong . Je peux y aller dans une minute et mettre à jour. BTW, Hashtable fait partie du cadre des collections .

J’utiliserais Apache Collections Lazy Map (pour initialiser les valeurs à 0) et utiliserais MutableIntegers d’Apache Lang comme valeurs dans cette carte.

Le plus gros coût consiste à effectuer deux recherches sur la carte dans votre méthode. Dans le mien tu dois le faire juste une fois. Obtenez simplement la valeur (elle sera initialisée si elle est absente) et incrémentez-la.

La structure de données TreeMap la bibliothèque Java fonctionnelle possède une méthode de update dans la dernière tête de réseau:

 public TreeMap update(final K k, final F f) 

Exemple d’utilisation:

 import static fj.data.TreeMap.empty; import static fj.function.Integers.add; import static fj.pre.Ord.ssortingngOrd; import fj.data.TreeMap; public class TreeMap_Update {public static void main(Ssortingng[] a) {TreeMap map = empty(ssortingngOrd); map = map.set("foo", 1); map = map.update("foo", add.f(1)); System.out.println(map.get("foo").some());}} 

Ce programme imprime “2”.

@Vilmantas Baranauskas: En ce qui concerne cette réponse, je voudrais dire si j’avais les points de rep, mais pas moi. Je voulais noter que la classe Counter définie ici n’est PAS thread-safe car elle n’est pas suffisante pour simplement synchroniser inc () sans synchroniser la valeur (). Les autres threads qui appellent value () ne sont pas sûrs de voir la valeur, à moins qu’une relation “venir avant” ait été établie avec la mise à jour.

Je ne sais pas à quel point il est efficace, mais le code ci-dessous fonctionne également. Vous devez définir une BiFunction au début. De plus, vous pouvez faire plus que simplement incrémenter avec cette méthode.

 public static Map strInt = new HashMap(); public static void main(Ssortingng[] args) { BiFunction bi = (x,y) -> { if(x == null) return y; return x+y; }; strInt.put("abc", 0); strInt.merge("abc", 1, bi); strInt.merge("abc", 1, bi); strInt.merge("abc", 1, bi); strInt.merge("abcd", 1, bi); System.out.println(strInt.get("abc")); System.out.println(strInt.get("abcd")); } 

la sortie est

 3 1 

Si vous utilisez les collections Eclipse , vous pouvez utiliser un HashBag . Ce sera l’approche la plus efficace en termes d’utilisation de la mémoire et elle fonctionnera également bien en termes de vitesse d’exécution.

HashBag est soutenu par un MutableObjectIntMap qui stocke les ints primitifs au lieu des objects Counter . Cela réduit la surcharge de mémoire et améliore la vitesse d’exécution.

HashBag fournit l’API dont vous avez besoin car c’est une Collection qui vous permet également de rechercher le nombre d’occurrences d’un élément.

Voici un exemple tiré des collections Kata d’Eclipse .

 MutableBag bag = HashBag.newBagWith("one", "two", "two", "three", "three", "three"); Assert.assertEquals(3, bag.occurrencesOf("three")); bag.add("one"); Assert.assertEquals(2, bag.occurrencesOf("one")); bag.addOccurrences("one", 4); Assert.assertEquals(6, bag.occurrencesOf("one")); 

Note: Je suis un committer pour les collections Eclipse.

Étant donné que beaucoup de personnes recherchent des sujets Java pour les réponses Groovy, voici comment vous pouvez le faire dans Groovy:

 dev map = new HashMap() map.put("key1", 3) map.merge("key1", 1) {a, b -> a + b} map.merge("key2", 1) {a, b -> a + b}