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

377

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.

Gregory
la source
Je pense que ce serait la même chose pour java.util.Hashtable.
jrudolph
2
Bien sûr, ce serait la même chose, car Hashtable est en fait une carte.
whiskeysierra
Java 8: exemple computeIfAbsent: stackoverflow.com/a/37439971/1216775
akhil_mittal

Réponses:

367

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();
}
Gregory
la source
3
Excellent travail, bravo. Un commentaire mineur - l'appel putIfAbsent () dans le code AtomicLong instanciera un nouveau AtomicLong (0) même si l'un est déjà dans la carte. Si vous modifiez ceci pour utiliser if (map.get (key) == null) à la place, vous obtiendrez probablement une amélioration de ces résultats de test.
Leigh Caldwell
2
J'ai fait la même chose récemment avec une approche similaire à MutableInt. Je suis content d'apprendre que c'était la solution optimale (je pensais juste que c'était sans faire de tests).
Kip
4
Dans le cas d'Atomic Long, ne serait-il pas plus efficace de le faire en une seule étape (vous n'avez donc qu'une seule opération get coûteuse au lieu de 2) "map.putIfAbsent (word, new AtomicLong (0)). IncrementAndGet ();"
smartnut007
1
Vous ne comparez pas les pommes aux pommes ici. Aucune des autres options n'est compatible avec les threads, donc la version Atomic devrait utiliser une normale HashMap, pas une ConcurrentHashMap, pour une comparaison égale. Ce devrait également être un AtomicInteger, et non un AtomicLong, pour une comparaison égale. --- De plus, an int[1]serait une simple version intégrée de MutableInt, ne nécessitant pas de nouvelle classe.
Andreas
1
@gregory avez-vous pensé à Java 8 freq.compute(word, (key, count) -> count == null ? 1 : count + 1)? En interne, il fait une recherche moins hachée que containsKey, il serait intéressant de voir comment il se compare aux autres, en raison de la lambda.
TWiStErRob
255

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 .

LE GALL Benoît
la source
aime toujours java 8. Est-ce atomique? ou dois-je l'entourer d'un synchronisé?
Tiina
4
cela n'a pas semblé fonctionner pour moi mais l'a map.merge(key, 1, (a, b) -> a + b); fait
russter
2
Les caractéristiques de @Tiina Atomicity sont spécifiques à l'implémentation, cf. the docs : "L'implémentation par défaut ne garantit pas les propriétés de synchronisation ou d'atomicité de cette méthode. Toute implémentation fournissant des garanties d'atomicité doit remplacer cette méthode et documenter ses propriétés de concurrence. En particulier, toutes les implémentations de la sous-interface ConcurrentMap doivent documenter si la fonction est appliquée une fois atomiquement que si la valeur n'est pas présente. "
jensgram
2
Pour groovy, il n'accepterait pas Integer::sumcomme BiFunction, et n'aimait pas que @russter réponde comme il était écrit. Cela a fonctionné pour moiMap.merge(key, 1, { a, b -> a + b})
jookyone
2
@russter, je sais que votre commentaire remonte à plus d'un an, mais vous souvenez-vous justement pourquoi cela n'a pas fonctionné pour vous? Avez-vous eu une erreur de compilation ou la valeur n'a-t-elle pas été incrémentée?
Paul
44

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:

leventov
la source
2
Merci, c'était vraiment utile. Il serait intéressant d'ajouter le multiset de Guava (par exemple, HashMultiset) à la référence.
cabad
34

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); 
H6.
la source
7
AtomicLongMap#getAndAddprend une primitive longet non la classe wrapper; ça ne sert à rien new Long(). Et AtomicLongMapest un type paramétré; vous auriez dû le déclarer comme AtomicLongMap<String>.
Helder Pereira
32

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

Hank Gay
la source
9
PutIfAbsent () renvoie la valeur. Cela pourrait être une grande amélioration de stocker la valeur retournée dans une variable locale et de l'utiliser pour incrementAndGet () plutôt que d'appeler get à nouveau.
smartnut007
putIfAbsent peut renvoyer une valeur nulle si la clé spécifiée n'est pas déjà associée à une valeur à l'intérieur de Map, donc je serais prudent d'utiliser la valeur retournée. docs.oracle.com/javase/8/docs/api/java/util/…
bumbur
27
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!

off99555
la source
La méthode getOfDefault n'est pas disponible dans JAVA 7. Comment puis-je y parvenir dans JAVA 7?
tanvi
1
Vous devrez alors peut-être vous fier à d'autres réponses. Cela ne fonctionne qu'en Java 8.
off99555
1
+1 pour la solution de fusion, ce sera la fonction la plus performante car vous ne devez payer qu'une seule fois pour le calcul du code de hachage (dans le cas où la carte sur laquelle vous l'utilisez prend correctement en charge la méthode), au lieu de potentiellement la payer 3 de départ
Ferrybig
2
Utilisation de l'inférence de méthode: map.merge (key, 1, Integer :: sum)
earandap
25

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.

Chris Nokleberg
la source
La réponse ci-dessus doit refléter la réponse de tovares. L'API a changé depuis sa publication (il y a 3 ans :))
Steve
La count()méthode sur un multiset s'exécute-t-elle en temps O (1) ou O (n) (pire cas)? Les documents ne sont pas clairs sur ce point.
Adam Parkin
Mon algorithme pour ce genre de chose: if (hasApacheLib (thing)) return apacheLib; sinon si (hasOnGuava (chose)) retourne la goyave. Habituellement, je ne dépasse pas ces deux étapes. :)
digao_mb
22

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.

Aleksandar Dimitrov
la source
Pour éviter le problème des valeurs initiales non mappées / nulles dans groovy, je finis par faire: counts.put (clé, (count.get (clé)?: 0) + 1) // version trop complexe de ++
Joe Atzberger
2
Ou, plus simplement: count = [:]. WithDefault {0} // ++ absent
Joe Atzberger
18

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.

Philip Helger
la source
5
Vous ne voulez pas démarrer le MutableInt à 1 la première fois que vous le mettez dans la carte?
Tom Hawtin - tackline
5
Le commons-lang d'Apache a un MutableInt déjà écrit pour vous.
SingleShot
11

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.

akhil_mittal
la source
pourquoi concurrentHashmap et AtomicLong?
ealeon
7

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

volée
la source
5

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);
Intelligent
la source
3

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


la source
3

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.

tovare
la source
3

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.

jrudolph
la source
Le lien vers TObjectIntHashMap est rompu. C'est le lien correct: trove4j.sourceforge.net/javadocs/gnu/trove/map/…
Erel Segal-Halevi
Merci, Erel, j'ai corrigé le lien.
jrudolph
3

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);
Eamonn O'Brien-Strain
la source
3

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

le felis leo
la source
3

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

map.put(key, map.getOrDefault(key, 0) + 1);
sudoz
la source
Cela n'incrémente pas la valeur, il définit simplement la valeur actuelle ou 0 si aucune valeur n'a été affectée à la clé.
siegi
Vous pouvez augmenter la valeur de ++... OMG, c'est si simple. @siegi
sudoz
Pour mémoire: ++ne fonctionne nulle part dans cette expression car une variable est nécessaire comme opérande mais il y a juste des valeurs. Votre ajout d' + 1œuvres cependant. Maintenant, votre solution est la même que dans la réponse off99555s .
siegi
2

"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
  }
}
le felis leo
la source
1

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 .

Hank Gay
la source
1

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.

jb.
la source
1

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

Apocalisp
la source
1

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

Alex Miller
la source
Si vous souhaitez référencer la réponse de quelqu'un, utilisez @ [Nom d'utilisateur] en haut, par exemple, @Vilmantas Baranauskas <Le contenu va ici>
Hank Gay
J'ai fait cette modification pour le nettoyer.
Alex Miller
1

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
MGoksu
la source
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.

Craig P. Motlin
la source
1

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);
Eugene Chung
la source
mymap.merge(key, 1, Integer::sum)?
Det
-2

É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}
Keith
la source
-2

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();
Assaduzzaman Assad
la source
-3

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!

ggaugler
la source