La manière la plus efficace d'incrémenter une valeur de carte en Java

OK, peut - être une vieille question, mais il y a un chemin plus court avec Java 8:

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

ce qu'il fait : si clé n'existe pas, mettre 1 comme valeur, sinon somme 1 à la valeur liée à clé . En savoir plus ici

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

les Meilleurs résultats par la méthode (petit, c'est mieux):

                 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 Time\space:

@Hank Gay

comme suite à mon propre commentaire (plutôt inutile): Trove ressemble à la voie à suivre. Si, pour une raison quelconque, vous vouliez vous en tenir à la norme JDK, ConcurrentMap et AtomicLong peut rendre le code un minuscule un peu plus agréable, bien que 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 . De façon réaliste, a augmenté la convivialité au filetage est tout ce que cette approche doit recommander.

Google Goyave est votre ami...

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

E. G.

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

également possible d'ajouter 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();
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 des clés/entrées, etc. Sur le plan interne , l'implémentation utilise actuellement un HashMap<E, AtomicInteger> , vous n'aurez donc pas à engager de frais de boxe.

Vous devez être conscient du fait que l'original de votre tentative de

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 exécute une opération potentiellement assez similaire au second, donc vous faites le même travail deux fois !

si vous regardez L'API pour la Map, get les opérations renvoient habituellement null lorsque la map ne contient l'élément demandé.

notez que cela fera une solution comme

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

dangereux, puisqu'il pourrait donner NullPointerException s. Vous devriez vérifier pour un null d'abord.

Aussi la note , et c'est très important, que HashMap s peut contenir nulls par définition. Donc pas tous les revenus null dit" là est aucun élément". À cet égard, containsKey se comporte différemment de get en vous disant réellement si Il ya un tel élément. Reportez-vous à L'API pour plus de détails.

Pour votre cas, cependant, vous pourriez ne pas vouloir distinguer entre un null stocké et "noSuchElement". Si vous ne voulez pas permettre null s, vous pourriez préférer un Hashtable . À l'aide d'un wrapper bibliothèque comme déjà proposé dans d'autres réponses pourrait être une meilleure solution au traitement manuel, en fonction de la complexité de votre application.

Pour compléter la réponse (et j'ai oublié de mettre que la première, grâce à la fonction d'édition!), la meilleure façon de le faire nativement, est de get dans un "1519180920 variable", case à cocher pour null et put avec un 1 . La variable devrait être final parce qu'elle est immuable de toute façon. Le compilateur n'a peut-être pas besoin de cet indice, mais il est plus clair de cette façon.

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 vous fier à l'autoboxing, vous devriez dire quelque chose comme map.put(new Integer(1 + i.getValue())); à la 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 la création d'un objet supplémentaire, mais le overhead par rapport à la création d'un entier (même avec entier.valeur de) ne devrait pas être tellement.

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

et c'est comme ça qu'on incrémente une valeur avec du code simple.

prestation:

• ne Pas créer une autre classe pour mutable int
• code Court
• facile à comprendre
• no null point exception

une Autre façon est d'utiliser la méthode de fusion, mais c'est trop juste pour 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 du temps.

rotation de mémoire peut être un problème ici, puisque chaque boxe d'un int supérieur ou égal à 128 provoque une allocation d'objet (voir entier.valueOf (int)). Bien que le ramasseur d'ordures s'occupe très efficacement des objets éphémères, la performance en souffrira jusqu'à un certain point.

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 support int à la place. Phax a déjà présenté le code pour ce. Ici encore, avec deux changements (classe de support rendue statique et valeur initiale fixée à 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 qui est directement adaptée aux types de valeurs primitives. 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.obtenez et vérifiez si la valeur retournée est nulle ou pas.

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

vous pouvez faire usage de computeIfAbsent méthode dans Map interface 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 computeIfAbsent vérifie si la clé spécifiée est déjà associée à une valeur ou non? Si aucune valeur associée alors il tente de calculer sa valeur en utilisant la fonction de cartographie donnée. En tout cas, il renvoie l'existant (ou calculée) valeur 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 oeil à la classe LongAdder .Sous haute assertion , le débit prévu de cette classe est nettement plus élevé que AtomicLong , au détriment d'une plus grande consommation d'espace.

Êtes-vous sûr que c'est un goulot d'étranglement? Avez-vous fait une analyse de performance?

essayez D'utiliser le profileur NetBeans (son libre et intégré dans NB 6.1) pour regarder les points chauds.

enfin, une mise à niveau JVM (disons de 1.5->1.6) est souvent un booster de performance bon marché. Même une mise à niveau dans le numéro de construction peut fournir de bonnes performances boosts. Si vous utilisez Windows et qu'il s'agit d'une application de classe serveur, utilisez-server sur la ligne de commande pour utiliser Server Hotspot JVM. Sur les machines Linux et Solaris, c'est autodétecté.

Il ya un couple d'approches:

1. utilisez un sac alorithm comme les ensembles contenus dans les Collections Google.

2. créer conteneur mutable que vous pouvez utiliser sur la carte:

    class My{
        String word;
        int count;
    }

Et utilisez put("mot", " Mon("Mot") ); vous pouvez Ensuite vérifier s'il existe et l'incrément lors de l'ajout.

évitez de rouler votre propre solution l'utilisation de listes, parce que si vous obtenez innerloop recherche et le tri, votre performance sera puante. La première solution de HashMap est en fait assez rapide, mais un bon comme celui trouvé dans les Collections de Google est probablement mieux.

Compter des mots en utilisant des Collections Google, ressemble à quelque chose comme ceci:

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

utiliser le HashMultiset est assez élégant, parce qu'un algorithme de poche est exactement ce dont vous avez besoin quand vous comptez des mots.

je pense que votre solution serait la voie standard, mais - comme vous l'avez vous - même noté-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 Mutabilint qui pourrait être encore plus rapide, si un peu d'un hack, est d'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 si vous pouviez relire vos tests de performance avec cette variation. Il pourrait être le plus rapide.

Edit: le modèle ci-dessus a bien fonctionné pour moi, mais finalement j'ai changé pour utiliser les collections de Trove pour réduire la taille de la mémoire dans certaines cartes très grandes j'étais créer -- et en bonus, c'était aussi plus rapide.

une caractéristique vraiment agréable est que la classe TObjectIntHashMap a un seul appel adjustOrPutValue qui, selon qu'il y a déjà une valeur à cette clé, va soit mettre une valeur initiale ou incrémenter la valeur existante. C'est parfait pour incrémenter:

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

Google Collections HashMultiset:

- très élégant à utiliser

- mais consommer CPU et mémoire

le Mieux serait d'avoir une méthode comme : Entry<K,V> getOrPut(K); (élégant, et de faible coût)

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

plus élégant:

- prendre un HashSet<Entry>

- étendre de sorte que get(K) mettre une nouvelle Entrée si nécessaire

- L'entrée pourrait être votre propre objet.

-- > (new MyHashSet()).get(k).increment();

"" besoin "get" (pour s'assurer qu'aucun double de la clé).

Donc directement faire un "put",

et s'il y avait une valeur précédente, alors 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 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
}

avis: ce code n'est pas sûr. Utilisez - le pour construire puis utilisez la carte, pas pour la mettre à jour simultanément.

"1519120920 d'Optimisation": Dans une boucle, garder 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érentes enveloppes primitives, par exemple, Integer sont immuables donc il n'y a vraiment pas une façon plus concise de faire ce que vous demandez à moins que vous pouvez le faire avec quelque chose comme AtomicLong . Je peux essayer dans une minute et me mettre à jour. BTW, table de hachage est une partie de la Collections "Cadre de 151950920" .

j'utiliserais Apache Collections Lazy Map (pour initialiser les valeurs à 0) et J'utiliserais des Mutablintegers D'Apache Lang comme valeurs dans cette carte.

le plus gros coût est d'avoir à séracher la carte deux fois dans votre méthode. Dans le mien, il ne faut le faire qu'une fois. Juste obtenir la valeur (initialisé si absent) et de l'incrémenter.

l'infrastructure de données Java fonctionnel bibliothèque TreeMap a une méthode update dans la dernière tête de tronc:

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

exemple d'usage:

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 rep, mais je ne le fais pas. Je voulais noter que la classe Counter définie n'est pas thread-safe car il n'est pas suffisant de simplement synchroniser inc() sans valeur de synchronisation(). Les autres threads appelant la valeur () ne sont pas garantis pour voir la valeur à moins qu'une relation arrive-avant qu'elle n'ait été établie avec la mise à jour.

Je ne sais pas si c'est efficace, mais le code ci-dessous fonctionne aussi.Vous devez définir un BiFunction au 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"));
}

sortie est

3
1

si vous utilisez Eclipse Collections , vous pouvez utiliser un HashBag . Il sera l'approche la plus efficace en termes d'utilisation de la mémoire et elle jouera aussi bien en termes de vitesse d'exécution.

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

HashBag fournit l'API dont vous avez besoin depuis c'est un Collection qui vous permet également de requête pour le nombre d'occurrences d'un élément.

voici un exemple tiré du Eclipse Collections 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"));

Note: je suis un committer pour les Collections Eclipse.

depuis que beaucoup de gens cherchent des sujets Java pour des réponses Groovy, voici comment vous pouvez le faire 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}