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

https://stackoverflow.com/questions/81346

09-06-2019
|

Question

J'espère que cette question n'est pas considérée comme trop élémentaire pour ce forum, mais nous verrons. Je me demande comment refactoriser du code pour obtenir de meilleures performances qui s'exécutent plusieurs fois.

Dites que je crée une liste de fréquence de mots, en utilisant une carte (probablement une carte de hachage), 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 comment je le fais actuellement:

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

Qui s'appuie bien sûr sur la fonctionnalité de sélection automatique dans les nouvelles versions de Java. Je me demande si vous pouvez suggérer un moyen plus efficace d’augmenter une telle valeur. Existe-t-il même de bonnes raisons de performance pour éviter le framework Collections et utiliser quelque chose d'autre?

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

La solution

Quelques résultats de test

J'ai eu beaucoup de bonnes réponses à cette question - merci les gens - alors j'ai décidé de faire quelques tests et de déterminer quelle méthode est réellement la plus rapide. Les cinq méthodes que j'ai testées sont les suivantes:

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

Méthode

Voici ce que j'ai fait ...

a 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 mots du fichier. Comme cela ne prenait en moyenne que 3 secondes, je l’ai demandé d’effectuer le comptage de fréquence (et non les E / S) 10 fois.
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) essentiellement en utilisant
a effectué les cinq tests en série, puis trois autres fois.

a fait la 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 (référence)
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 les méthodes MutableInt et Trove soient nettement plus rapides, en ce sens qu’elles donnent un gain de performances de plus de 10%. Cependant, si le filetage pose problème, AtomicLong pourrait être plus attrayant que les autres (je ne suis pas vraiment sûr). J'ai également exécuté TestForNull avec final variables, mais la différence était négligeable.

Notez que je n'ai pas défini l'utilisation de la mémoire dans les différents scénarios. Je serais heureux d’entendre les personnes qui ont une bonne idée de la manière dont les méthodes MutableInt et Trove pourraient influer sur 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 découvre des problèmes, c'est la voie que je vais le plus probablement 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();

Découverte

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

Autres conseils

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

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

Ce que ça fait: si la clé n'existe pas, donnez-lui 1 , sinon somme 1 à la valeur liée à clé . Plus d'informations ici

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

Meilleurs résultats par méthode (plus petit 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 temps \ espace:

Google Goyave est votre ami ...

... au moins dans certains cas. Ils ont cette belle AtomicLongMap . Particulièrement agréable, car vous traitez avec long comme valeur dans votre carte.

ex.

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

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

map.getAndAdd(word, 112L);

@Hank Gay

Pour faire suite à mon propre commentaire (plutôt inutile): Trove semble être la voie à suivre. Si, pour une raison quelconque, vous souhaitez conserver le kit JDK standard, ConcurrentMap et AtomicLong peut rendre le code un minuscule peu plus joli, 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 manière réaliste, cette approche ne peut que le recommander.

C'est toujours une bonne idée de consulter la bibliothèque Google Collections de ce type. de chose. Dans ce cas, il s'agit d'un multiset . fera le tour:

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 semblables à celles de la carte pour effectuer une itération sur les clés / entrées, etc. En interne, la mise en oeuvre utilise actuellement un HashMap<E, AtomicInteger>, vous évitant ainsi des 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 assez similaire au second, vous effectuez donc le même travail deux fois !

Si vous examinez l'API pour la carte, null les opérations renvoient généralement NullPointerException lorsque la carte ne contient pas l'élément demandé.

Notez que cela créera une solution comme

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

dangereux, car cela pourrait donner HashMap s. Vous devriez commencer par vérifier nulls.

Notez également , et cela est très important, que Hashtable s peut contenir final par définition. Ainsi, tous les put retournés ne disent pas & "Il n’existe pas un tel élément &"; À cet égard, 1 se comporte différemment par rapport à map.put(new Integer(1 + i.getValue())); en vous disant si il existe un tel élément. Reportez-vous à l'API pour plus de détails.

Toutefois, dans votre cas, vous ne voudrez peut-être pas faire la distinction entre un <=> <>> et & "NoSuchElement &" Stocké. Si vous ne souhaitez pas autoriser <=>, vous préférerez peut-être un <=>. Utiliser une bibliothèque de wrapper, comme cela avait déjà été proposé dans d’autres réponses, pourrait constituer une meilleure solution au traitement manuel, en fonction de la complexité de votre application.

Pour compléter la réponse (et j’avais oublié de le préciser au début, grâce à la fonction de modification!), la meilleure façon de le faire en mode natif consiste à <=> créer une <=> variable, recherchez <= > et <=> avec un <=>. La variable doit être <=> car 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 souhaitez pas vous fier à la sélection automatique, vous devez plutôt indiquer quelque chose comme <=>.

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 ainsi que vous incrémentez une valeur avec un code simple.

Avantage:

Ne pas créer une autre classe pour mutable int
Code abrégé
Facile à comprendre
Aucune exception de pointeur null

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: la plupart du temps, la lisibilité du code doit être au cœur de la lisibilité du code.

Une autre solution 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 la surcharge par rapport à la création d’un entier (même avec Integer.valueOf) ne devrait pas être si importante.

Vous pouvez utiliser computeIfAbsent dans Map l'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? 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 retourne la valeur actuelle (existante ou calculée) associée à la clé spécifiée, ou null si la valeur calculée est null.

Si vous avez une situation où plusieurs threads mettent à jour une somme commune, vous pouvez consulter LongAdder class.Un niveau de contention élevé, le débit attendu de cette classe est nettement supérieur à AtomicLong, au détriment d'une consommation d'espace plus importante.

La rotation de la mémoire peut être un problème ici, car chaque mise en boîte d'un int supérieur ou égal à 128 entraîne une allocation d'objet (voir Integer.valueOf (int)). Bien que le ramasse-miettes traite très efficacement les objets éphémères, les performances en souffriront dans une certaine mesure.

Si vous savez que le nombre d'incréments réalisés sera largement supérieur au nombre de clés (= mots dans ce cas), envisagez d'utiliser un détenteur int à la place. Phax a déjà présenté du code pour cela. La voici à nouveau, avec deux modifications (la classe de titulaire est définie sur statique et la valeur initiale est 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 Map directement adaptée aux types de valeur primitifs. jrudolph a mentionné la trace GNU .

Au fait, 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 null 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 de performance?

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

Enfin, une mise à niveau de la machine virtuelle Java (par exemple de 1.5 - > 1.6) est souvent un booster de performance bon marché. Même une mise à niveau du numéro de version peut fournir de bonnes augmentations 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 Server Hotspot. Sur les machines Linux et Solaris, cela est détecté automatiquement.

Il existe plusieurs approches:

Utilisez un algorithme semblable à celui des ensembles contenus dans Google Collections.
Créez un conteneur modifiable que vous pouvez utiliser dans la carte:


    class My{
        String word;
        int count;
    }

Et utilisez put (& "; mot &"; nouveau my (& "; mot &";)); Ensuite, vous pouvez vérifier s'il existe et incrémenter lors de l'ajout.

Évitez de faire rouler votre propre solution en utilisant des listes, car si vous effectuez une recherche et un tri dans Inloop, vos performances seront mauvaises. La première solution HashMap est en fait assez rapide, mais une solution similaire à celle trouvée dans Google Collections est probablement meilleure.

Le décompte des mots à l'aide de Google Collections ressemble à ceci:



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

Utiliser HashMultiset est très élégant, car un algorithme de type sac est exactement ce dont vous avez besoin pour compter les mots.

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

Vous pouvez consulter Trace GNU . C'est une bibliothèque qui contient toutes sortes de collections primitives rapides. Votre exemple utiliserait un TObjectIntHashMap doté d'une méthode adjustOrPutValue qui fait exactement ce que vous voulez.

Une variante de l'approche MutableInt qui pourrait être encore plus rapide consiste à utiliser un tableau entier à 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 de pouvoir relancer vos tests de performance avec cette variante. C'est peut-être le plus rapide.

Éditer: le motif ci-dessus a bien fonctionné pour moi, mais j'ai finalement décidé d'utiliser les collections de Trove afin de réduire la taille de la mémoire sur certaines très grandes cartes que je créais - et en prime, cela a également été plus rapide.

Une caractéristique vraiment intéressante est que la TObjectIntHashMap classe a un seul adjustOrPutValue appel qui, selon qu’il existe déjà une valeur à cette clé, mettra une valeur initiale ou augmentera 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 processeur et de la mémoire

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

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

Plus élégant:
- prenez un HashSet<Entry>
- étendez-le de sorte que get(K) mette une nouvelle entrée si nécessaire
- L’entrée pourrait être votre propre objet.
- > (new MyHashSet()).get(k).increment();

& "mettre &"; besoin de " obtenir " (pour éviter toute duplication de clé).
Alors faites directement un & "Mettre &" ;,
et s'il y avait une valeur précédente, faites une addition:

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 nombre 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, et non pour la mettre à jour simultanément.

Optimisation: Dans une boucle, conservez l'ancienne valeur pour qu'elle devienne 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 Integer sont immuables. Il n'y a donc pas de moyen plus concis de faire ce que vous demandez à moins que ne le fassiez avec quelque chose comme AtomicLong . Je peux y aller dans une minute et mettre à jour. BTW, Hashtable fait-il partie du Collections Framework .

J'utiliserais Apache Collections Lazy Map (pour initialiser les valeurs à 0) et utiliserais MutableIntegers d'Apache Lang en tant que valeurs dans cette carte.

Le coût le plus élevé est de devoir rechercher la carte deux fois dans votre méthode. Dans le mien, vous devez le faire juste une fois. Obtenez juste la valeur (elle sera initialisée si elle est absente) et incrémentez-la.

La base de données TreeMap de la bibliothèque Java fonctionnelle contient une méthode update dans la dernière tête de coffre:

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 voudrais commenter si j'avais les points de repère, mais ce n'est pas le cas. Je voulais noter que la classe Counter définie ici N'EST PAS thread-safe, car il ne suffit pas de synchroniser inc () sans synchroniser value (). Les autres threads appelant value () ne sont pas assurés de voir la valeur, sauf si une relation passe-avant a été établie avec la mise à jour.

Je ne sais pas dans quelle mesure il est efficace, mais le code ci-dessous fonctionne également. 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"));
}

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.

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

<=> fournit l'API dont vous auriez besoin, car il s'agit d'un <=> qui vous permet également d'interroger le nombre d'occurrences d'un élément.

Voici un exemple tiré du Kata de collections Eclipse .

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 partisan des collections Eclipse.

Assez simple, utilisez simplement la fonction intégrée dans Map.java comme suit

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

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

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}

En espérant que je comprends bien votre question, je viens de Java depuis Python pour pouvoir comprendre votre lutte.

si vous avez

map.put(key, 1)

vous feriez

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

J'espère que ça aide!

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow