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 basique pour ce forum, mais nous verrons. Je me demande comment refactoriser du code pour de meilleures performances qui s'exécutent plusieurs fois.

Supposons que je crée une liste de fréquence de mots, en utilisant une carte (probablement un 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 jeton du mot est trouvé.

En Perl, incrémenter 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 mise en boîte automatique dans les nouvelles versions de Java. Je me demande si vous pouvez suggérer un moyen plus efficace d'augmenter une telle valeur. Y a-t-il même de bonnes raisons de performance pour éviter le framework Collections et utiliser quelque chose d'autre à la place?

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

Quelques résultats de tests

J'ai obtenu beaucoup de bonnes réponses à cette question - merci les gens - j'ai donc décidé d'exécuter des tests et de 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" 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 à l'exception des différences 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 décompte de fréquence de tous les jetons de mot du fichier. Comme cela ne prenait en moyenne que 3 secondes, je l'ai fait effectuer le décompte de fréquences (pas les E / S) 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 d'horloge) essentiellement en utilisant la méthode de Ian Darwin dans le Java Cookbook .
3. effectué les cinq tests en série, puis l'a fait trois fois de plus.
4. moyenne des 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.

La méthode ContainsKey était, comme prévu, 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 (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, en ce qu'elles seules donnent une amélioration des performances de plus de 10%. Cependant, si le filetage 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 des finalvariables, 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 heureux d'entendre tous ceux qui ont une bonne idée de la façon dont les méthodes MutableInt et Trove seraient 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 aucun chargement de classes tierces. Donc, sauf si je découvre des problèmes, c'est la voie que je suis le plus susceptible d'aller.

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();
}

Maintenant, il existe un moyen plus court avec Java 8 Map::merge.

myMap.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 .

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

Meilleurs résultats par méthode (plus petit est meilleur):

                 time, ms
kolobokeCompile  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

Résultats temps \ espace:

Google Guava est votre ami ...

... au moins dans certains cas. Ils ont cette belle AtomicLongMap . Particulièrement agréable parce que vous avez affaire à longue que la valeur de 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); 

@Hank Gay

Pour faire suite à mon propre commentaire (plutôt inutile): Trove ressemble à la voie à suivre. Si, pour une raison quelconque, vous vouliez coller avec le JDK standard, ConcurrentMap et AtomicLong peuvent rendre le code un petit de plus agréable bits, bien que YMMV.

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

laissera 1la valeur dans la carte pour foo. De façon réaliste, une convivialité accrue pour le filetage est tout ce que cette approche doit le recommander.

Map<String, Integer> map = new HashMap<>();
String key = "a random key";
int count = map.getOrDefault(key, 0); // ensure count will be one of 0,1,2,3,...
map.put(key, count + 1);

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

Avantage:

• Pas besoin d'ajouter une nouvelle classe ou d'utiliser un autre concept de mutable int
• Ne compte sur aucune bibliothèque
• Facile à comprendre ce qui se passe exactement (pas trop d'abstraction)

Inconvénient:

• La carte de hachage sera recherchée deux fois pour get () et put (). Ce ne sera donc pas le code le plus performant.

Théoriquement, une fois que vous appelez get (), vous savez déjà où mettre (), vous ne devriez donc pas avoir à chercher à nouveau. Mais la recherche dans la carte de hachage prend généralement très peu de temps pour ignorer ce problème de performances.

Mais si vous êtes très sérieux à propos de ce problème, vous êtes un perfectionniste, une autre façon est d'utiliser la méthode de fusion, c'est (probablement) plus efficace que l'extrait de code précédent car vous ne chercherez (théoriquement) la carte qu'une seule fois: (bien que ce code n'est pas évident à première vue, il est court et performant)

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

Suggestion: la plupart du temps, vous devriez vous soucier de la lisibilité du code plutôt que de peu de gain de performances. Si le premier extrait de code est plus facile à comprendre, utilisez-le. Mais si vous êtes en mesure de bien comprendre le 2e, alors vous pouvez aussi y aller!

C'est toujours une bonne idée de consulter la bibliothèque Google Collections pour ce genre de chose. 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 carte pour itérer sur les clés / entrées, etc. En interne, l'implémentation utilise actuellement un HashMap<E, AtomicInteger>, donc vous n'encourrez pas de frais de boxe.

Vous devez être conscient du fait que votre tentative initiale

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

contient deux opérations potentiellement coûteuses sur une carte, à savoir containsKeyet get. Le premier effectue une opération potentiellement assez similaire au second, vous effectuez donc deux fois le même travail !

Si vous regardez l'API pour Map, les getopérations retournent généralement nulllorsque la map 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 entraîner l' NullPointerExceptional. Vous devriez vérifier pour une nullpremière.

Notez également , et c'est très important, que HashMaps peut contenir nullspar définition. Donc, tous les retours ne nulldisent pas "il n'y a pas un tel élément". À cet égard, containsKeyse comporte différemment de getvous dire si 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"noSuchElement" stocké. Si vous ne voulez pas autoriser, nullvous préférerezHashtable . L'utilisation d'une bibliothèque d'encapsuleurs comme cela a déjà été proposé dans d'autres réponses pourrait être une meilleure solution au traitement manuel, selon la complexité de votre application.

Pour compléter la réponse (et j'ai oublié de le mettre dans un premier temps, grâce à la fonction d'édition!), La meilleure façon de le faire en mode natif, est de placer getdans une finalvariable, de vérifier nullet de putle réintégrer avec un 1. La variable devrait être finalparce qu'elle est immuable de toute façon. Le compilateur n'a peut-être pas besoin de cet indice, mais c'est plus clair de cette façon.

carte HashMap finale = generateRandomHashMap ();
clé d'objet 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 mise en boîte automatique, vous devriez dire quelque chose comme à la map.put(new Integer(1 + i.getValue()));place.

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<String,MutableInt> map = new HashMap<String,MutableInt> ();
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 objet supplémentaire, mais la surcharge par rapport à la création d'un entier (même avec Integer.valueOf) ne devrait pas être tellement.

Vous pouvez utiliser la méthode computeIfAbsent dans l' Mapinterface fournie dans Java 8 .

final Map<String,AtomicLong> 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 computeIfAbsentvé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.

Sur une note latérale si vous avez une situation où plusieurs threads mettent à jour une somme commune, vous pouvez jeter un œil à LongAdder LongAdder.En cas de forte contention, le débit attendu de cette classe est nettement supérieur à AtomicLong, au détriment d'une consommation d'espace plus élevée.

La rotation de la mémoire peut être un problème ici, car chaque boxing d'un int supérieur ou égal à 128 provoque une allocation d'objet (voir Integer.valueOf (int)). Bien que le garbage collector traite très efficacement les objets à vie courte, les performances en souffriront dans une certaine mesure.

Si vous savez que le nombre d'incréments effectués sera largement supérieur au nombre de clés (= mots dans ce cas), envisagez d'utiliser un titulaire int à la place. Phax a déjà présenté le code pour cela. Le voici à nouveau, avec deux changements (classe de support rendue statique et valeur initiale définie sur 1):

static class MutableInt {
  int value = 1;
  void inc() { ++value; }
  int get() { return value; }
}
...
Map<String,MutableInt> map = new HashMap<String,MutableInt>();
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 de carte directement adaptée aux types de valeur primitifs. jrudolph a mentionné GNU Trove .

Soit dit en passant, 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 retournée est nulle ou non.

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

Êtes-vous sûr qu'il s'agit d'un goulot d'étranglement? Avez-vous effectué une analyse des performances?

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

Enfin, une mise à niveau JVM (disons de 1.5 à> 1.6) est souvent un booster de performances bon marché. Même une mise à niveau du numéro de build peut fournir de bonnes améliorations de performances. Si vous exécutez sous 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 Server. Sur les machines Linux et Solaris, cela est détecté automatiquement.

Il existe quelques approches:

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

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

    class My{
        String word;
        int count;
    }

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

Évitez de rouler votre propre solution à l'aide de listes, car si vous effectuez une recherche et un tri dans la boucle interne, vos performances seront nulles. La première solution HashMap est en fait assez rapide, mais une bonne comme celle trouvée dans Google Collections est probablement meilleure.

Compter les mots à l'aide de Google Collections ressemble à ceci:

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

L'utilisation de HashMultiset est assez élégante, car un algorithme de sac est exactement ce dont vous avez besoin pour compter les mots.

Je pense que votre solution serait la voie standard, mais - comme vous l'avez noté vous-même - ce n'est probablement pas la voie la 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 MutableInt qui pourrait être encore plus rapide, si elle est un peu un hack, consiste à utiliser un tableau int à un seul élément:

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

Il serait intéressant que vous puissiez réexécuter vos tests de performances 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 pour réduire la taille de la mémoire dans certaines très grandes cartes que je créais - et en bonus, il était également plus rapide.

Une fonctionnalité vraiment intéressante est que la TObjectIntHashMapclasse a un seul adjustOrPutValueappel qui, selon qu'il existe déjà une valeur à cette clé, mettra une valeur initiale ou incrémentera la valeur existante. C'est parfait pour incrémenter:

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

Google Collections HashMultiset:
- assez élégant à utiliser
- mais consomme du CPU et de la mémoire

Le mieux serait d'avoir une méthode comme: Entry<K,V> getOrPut(K); (élégante et à faible coût)

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

Plus élégant:
- prenez un HashSet<Entry>
- prolongez-le afin de get(K)mettre une nouvelle entrée si nécessaire
- l'entrée pourrait être votre propre objet.
->(new MyHashSet()).get(k).increment();

Assez simple, utilisez simplement la fonction intégrée Map.javacomme suit

map.put(key, map.getOrDefault(key, 0) + 1);

"put" nécessite "get" (pour garantir l'absence de clé en double).
Donc, 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 le décompte 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 créer puis utilisez la carte, pas pour la mettre à jour simultanément.

Optimisation: dans une boucle, conservez l'ancienne valeur pour devenir la nouvelle valeur de la boucle suivante.

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, Integersont immuables, il n'y a donc vraiment pas de manière plus concise de faire ce que vous demandez, sauf si vous pouvez le faire avec quelque chose comme AtomicLong . Je peux essayer ça 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 utiliser MutableIntegers d'Apache Lang comme valeurs dans cette carte.

Le plus gros coût est d'avoir à traquer la carte deux fois dans votre méthode. Dans le mien, vous ne devez le faire qu'une seule fois. Obtenez simplement la valeur (elle sera initialisée si elle est absente) et incrémentez-la.

La structure de données de la bibliothèque Java fonctionnelleTreeMap a une updateméthode dans la dernière tête de tronc:

public TreeMap<K, V> update(final K k, final F<V, V> f)

Exemple d'utilisation:

import static fj.data.TreeMap.empty;
import static fj.function.Integers.add;
import static fj.pre.Ord.stringOrd;
import fj.data.TreeMap;

public class TreeMap_Update
  {public static void main(String[] a)
    {TreeMap<String, Integer> map = empty(stringOrd);
     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 commenterais si j'avais les points de représentant, mais je n'en ai pas. Je voulais noter que la classe Counter définie il n'y a PAS de thread-safe car il ne suffit pas de synchroniser inc () sans synchroniser value (). Les autres threads appelant value () ne sont pas garantis pour voir la valeur sauf si une relation se produit avant a été établie avec la mise à jour.

Je ne sais pas à quel point c'est efficace, mais le code ci-dessous fonctionne aussi. Vous devez définir un BiFunctionau début. De plus, vous pouvez faire plus que simplement incrémenter avec cette méthode.

public static Map<String, Integer> strInt = new HashMap<String, Integer>();

public static void main(String[] args) {
    BiFunction<Integer, Integer, Integer> 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 des collections Eclipse , vous pouvez utiliser a 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.

HashBagest soutenu par un MutableObjectIntMapqui stocke les ints primitifs au lieu des Counterobjets. Cela réduit la surcharge de la mémoire et améliore la vitesse d'exécution.

HashBag fournit l'API dont vous auriez besoin car c'est un Collection vous permet également de rechercher le nombre d'occurrences d'un élément.

Voici un exemple tiré des collections Eclipse Kata .

MutableBag<String> 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"));

Remarque: je suis un committer pour les collections Eclipse.

Je suggère d'utiliser Java 8 Map :: compute (). Il considère également le cas où une clé n'existe pas.

Map.compute(num, (k, v) -> (v == null) ? 1 : v + 1);

Étant donné que de nombreuses personnes recherchent des réponses sur Groovy dans les rubriques Java, voici comment procéder dans Groovy:

dev map = new HashMap<String, Integer>()
map.put("key1", 3)

map.merge("key1", 1) {a, b -> a + b}
map.merge("key2", 1) {a, b -> a + b}

La manière simple et facile dans java 8 est la suivante:

final ConcurrentMap<String, AtomicLong> map = new ConcurrentHashMap<String, AtomicLong>();
    map.computeIfAbsent("foo", key -> new AtomicLong(0)).incrementAndGet();

J'espère que je comprends bien votre question, je viens de Java depuis Python afin que je puisse comprendre votre lutte.

si tu as

map.put(key, 1)

vous feriez

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

J'espère que cela t'aides!