Il modo più efficiente per incrementare un valore Map in Java

StackOverflow https://stackoverflow.com/questions/81346

  •  09-06-2019
  •  | 
  •  

Domanda

Spero che questa domanda non sia considerata troppo banale per questo forum, ma vedremo.Mi chiedo come eseguire il refactoring di un codice per prestazioni migliori che viene eseguito un sacco di volte.

Supponiamo che sto creando un elenco di frequenze di parole, utilizzando una mappa (probabilmente una HashMap), in cui ogni chiave è una stringa con la parola che viene conteggiata e il valore è un numero intero che viene incrementato ogni volta che viene trovato un token della parola.

In Perl, incrementare un tale valore sarebbe banalmente semplice:

$map{$word}++;

Ma in Java è molto più complicato.Ecco come lo sto facendo attualmente:

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

Che ovviamente si basa sulla funzionalità di autoboxing nelle versioni Java più recenti.Mi chiedo se puoi suggerire un modo più efficiente per incrementare tale valore.Ci sono anche buoni motivi di prestazioni per evitare il framework Collections e utilizzare invece qualcos'altro?

Aggiornamento:Ho fatto un test su molte delle risposte.Vedi sotto.

È stato utile?

Soluzione

Alcuni risultati dei test

Ho ottenuto molte buone risposte a questa domanda, grazie gente, quindi ho deciso di eseguire alcuni test e capire quale metodo è effettivamente più veloce.I cinque metodi che ho testato sono questi:

  • il metodo "ContainsKey" che ho presentato la domanda
  • il metodo "TestForNull" suggerito da Aleksandar Dimitrov
  • il metodo "AtomicLong" suggerito da Hank Gay
  • il metodo "Trove" suggerito da jrudolph
  • il metodo "MutableInt" suggerito da phax.myopenid.com

Metodo

Ecco cosa ho fatto...

  1. ha creato cinque classi identiche tranne che per le differenze mostrate di seguito.Ciascuna classe doveva eseguire un'operazione tipica dello scenario da me presentato:aprendo un file da 10 MB e leggendolo, quindi eseguendo un conteggio di frequenza di tutti i token di parole nel file.Poiché l'operazione ha richiesto in media solo 3 secondi, ho fatto eseguire il conteggio della frequenza (non l'I/O) 10 volte.
  2. cronometrato il ciclo di 10 iterazioni ma non l'operazione di I/O e registrato il tempo totale impiegato (in secondi di orologio) essenzialmente utilizzando Il metodo di Ian Darwin nel Java Cookbook.
  3. ha eseguito tutti e cinque i test in serie, quindi lo ha ripetuto altre tre volte.
  4. media dei quattro risultati per ciascun metodo.

Risultati

Presenterò prima i risultati e il codice di seguito per coloro che sono interessati.

IL Contiene la chiave metodo era, come previsto, il più lento, quindi fornirò la velocità di ciascun metodo rispetto alla velocità di quel metodo.

  • Contienechiave: 30.654 secondi (riferimento)
  • Atomicolungo: 29.780 secondi (1,03 volte più veloce)
  • ProvaPerNullo: 28.804 secondi (1,06 volte più veloce)
  • Raccolta: 26.313 secondi (1,16 volte più veloce)
  • MutableInt: 25.747 secondi (1,19 volte più veloce)

Conclusioni

Sembrerebbe che solo il metodo MutableInt e il metodo Trove siano significativamente più veloci, in quanto solo loro danno un aumento delle prestazioni di oltre il 10%.Tuttavia, se il threading è un problema, AtomicLong potrebbe essere più attraente degli altri (non ne sono proprio sicuro).Ho anche eseguito TestForNull con final variabili, ma la differenza era trascurabile.

Tieni presente che non ho profilato l'utilizzo della memoria nei diversi scenari.Sarei felice di sentire qualcuno che abbia buone informazioni su come i metodi MutableInt e Trove potrebbero influenzare l'utilizzo della memoria.

Personalmente trovo il metodo MutableInt il più interessante, poiché non richiede il caricamento di classi di terze parti.Quindi, a meno che non scopra problemi con esso, è molto probabile che andrò in questo modo.

Il codice

Ecco il codice cruciale di ciascun metodo.

Contiene la chiave

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

ProvaPerNull

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

Raccolta

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

Altri suggerimenti

OK, potrebbe essere una vecchia domanda, ma esiste una strada più breve con Java 8:

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

Cosa fa :Se chiave non esiste, metti 1 come valore, altrimenti somma 1 al valore collegato a chiave.Maggiori informazioni Qui

Una piccola ricerca nel 2016: https://github.com/leventov/java-word-count, codice sorgente di riferimento

Migliori risultati per metodo (più piccolo è meglio):

                 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

Risultati tempo\spazio:

Google Guaiava È tuo amico...

...almeno in alcuni casi.Hanno questo bello AtomicLongMap.Particolarmente bello perché hai a che fare con lungo come valore nella tua mappa.

Per esempio.

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

È anche possibile aggiungere più di 1 al valore:

map.getAndAdd(word, 112L);

@Hank Gay

A seguito del mio commento (piuttosto inutile):Trove sembra la strada da percorrere.Se, per qualsiasi motivo, volessi restare con il JDK standard, ConcurrentMap E AtomicLong può creare il codice a minuscolo un po' più carino, però YMMV.

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

lascerà 1 come valore nella mappa per foo.Realisticamente, una maggiore facilità di utilizzo del threading è tutto ciò che questo approccio può consigliare.

È sempre una buona idea dare un'occhiata a Libreria delle raccolte Google per questo genere di cose.In questo caso a Multiinsieme farà il trucco:

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

Esistono metodi simili a mappe per scorrere chiavi/voci, ecc.Internamente l'implementazione attualmente utilizza a HashMap<E, AtomicInteger>, quindi non dovrai sostenere costi di inscatolamento.

Dovresti essere consapevole del fatto che il tuo tentativo originale 

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

contiene due operazioni potenzialmente costose su una mappa, vale a dire containsKey E get.Il primo esegue un'operazione potenzialmente molto simile al secondo, quindi stai facendo lo stesso lavoro due volte!

Se guardi l'API per Map, get le operazioni di solito ritornano null quando la mappa non contiene l'elemento richiesto.

Nota che questo creerà una soluzione simile

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

pericoloso perché potrebbe cedere NullPointerExceptionS.Dovresti verificare la presenza di a null Primo.

Nota anche, e questo è molto importante, quello HashMapS Potere contenere nulls per definizione.Quindi non tutti sono tornati null dice "non esiste tale elemento".Nel rispetto, containsKey si comporta diversamente da get nel dirtelo davvero se esiste un elemento del genere.Fare riferimento all'API per i dettagli.

Nel tuo caso, tuttavia, potresti non voler distinguere tra un file stored null e "noSuchElement".Se non vuoi permetterlo nulls potresti preferire a Hashtable.L'utilizzo di una libreria wrapper come già proposto in altre risposte potrebbe essere una soluzione migliore al trattamento manuale, a seconda della complessità dell'applicazione.

Per completare la risposta (e all'inizio mi ero dimenticato di inserirlo, grazie alla funzione di modifica!), il modo migliore per farlo in modo nativo è quello di get in un final variabile, controlla null E put rientra con a 1.La variabile dovrebbe essere final perché comunque è immutabile.Il compilatore potrebbe non aver bisogno di questo suggerimento, ma in questo modo è più chiaro.

final HashMap map = generateRandomHashMap();
final Object key = fetchSomeKey();
final Integer i = map.get(key);
if (i != null) {
    map.put(i + 1);
} else {
    // do something
}

Se non vuoi fare affidamento sull'autoboxing, dovresti dire qualcosa del tipo map.put(new Integer(1 + i.getValue())); Invece.

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

Ed è così che incrementi un valore con un codice semplice.

Beneficio:

  • Non creare un'altra classe per int mutabile
  • Codice corto
  • Facile da capire
  • Nessuna eccezione di puntatore nullo

Un altro modo è utilizzare il metodo di unione, ma questo è troppo per incrementare semplicemente un valore.

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

Suggerimento:dovresti preoccuparti della leggibilità del codice più che di un piccolo guadagno di prestazioni nella maggior parte del tempo.

Un altro modo sarebbe creare un numero intero mutabile:

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

ovviamente questo implica la creazione di un oggetto aggiuntivo ma il sovraccarico rispetto alla creazione di un Integer (anche con Integer.valueOf) non dovrebbe essere così grande.

Puoi farne uso computaIfAbsent metodo dentro Map interfaccia fornita in Giava8. 

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]

Il metodo computeIfAbsent controlla se la chiave specificata è già associata a un valore o no?Se non è associato alcun valore, tenta di calcolarne il valore utilizzando la funzione di mappatura specificata.In ogni caso restituisce il valore corrente (esistente o calcolato) associato alla chiave specificata, oppure null se il valore calcolato è null.

Nota a margine: se hai una situazione in cui più thread aggiornano una somma comune, puoi dare un'occhiata LongAdder class.In condizioni di conflitto elevato, il throughput previsto di questa classe è significativamente superiore a AtomicLong, a scapito di un maggiore consumo di spazio.

La rotazione della memoria può essere un problema in questo caso, poiché ogni inscatolamento di un int maggiore o uguale a 128 provoca un'allocazione di oggetto (vedere Integer.valueOf(int)).Sebbene il garbage collector gestisca in modo molto efficiente gli oggetti di breve durata, le prestazioni ne risentiranno in una certa misura.

Se sai che il numero di incrementi effettuati supererà di gran lunga il numero di chiavi (= parole in questo caso), considera invece l'utilizzo di un contenitore int.Phax ha già presentato il codice per questo.Eccolo di nuovo, con due modifiche (classe titolare resa statica e valore iniziale impostato su 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();
}

Se hai bisogno di prestazioni estreme, cerca un'implementazione Map che sia direttamente adattata ai tipi di valore primitivi.ha menzionato jrudolph GNU Trove.

A proposito, un buon termine di ricerca per questo argomento è "istogramma".

Invece di chiamare contieneKey() è più veloce chiamare semplicemente map.get e verificare se il valore restituito è nullo o meno.

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

Sei sicuro che si tratti di un collo di bottiglia?Hai fatto qualche analisi delle prestazioni?

Prova a utilizzare il profiler NetBeans (è gratuito e integrato in NB 6.1) per esaminare gli hotspot.

Infine, un aggiornamento della JVM (ad esempio da 1.5->1.6) è spesso un miglioramento economico delle prestazioni.Anche un aggiornamento del numero di build può fornire buoni aumenti delle prestazioni.Se stai utilizzando Windows e questa è un'applicazione di classe server, utilizza -server sulla riga di comando per utilizzare la JVM Server Hotspot.Su macchine Linux e Solaris questo viene rilevato automaticamente.

Esistono un paio di approcci:

  1. Utilizza un algoritmo Bag come i set contenuti in Google Collections.

  2. Crea un contenitore mutabile che puoi utilizzare nella mappa:


    class My{
        String word;
        int count;
    }

E usa put("parola", new My("Parola") );Quindi puoi verificare se esiste e incrementare quando lo aggiungi.

Evita di lanciare la tua soluzione utilizzando gli elenchi, perché se esegui la ricerca e l'ordinamento del ciclo interno, le tue prestazioni pezzeranno.La prima soluzione HashMap è in realtà abbastanza veloce, ma probabilmente è migliore una vera e propria come quella trovata in Google Collections.

Contare le parole utilizzando Google Collections è simile a questo:



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

Usare HashMultiset è abbastanza elegante, perché un algoritmo bag è proprio ciò di cui hai bisogno quando conti le parole.

Penso che la tua soluzione sarebbe il modo standard, ma, come hai notato tu stesso, probabilmente non è il modo più veloce possibile.

Potresti guardare GNU Trove.Questa è una libreria che contiene tutti i tipi di collezioni primitive e veloci.Il tuo esempio utilizzerebbe a TObjectIntHashMap che ha un metodo adjustmentOrPutValue che fa esattamente quello che vuoi.

Una variazione dell'approccio MutableInt che potrebbe essere ancora più veloce, anche se un po' complicata, consiste nell'utilizzare un array int a elemento singolo: 

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];

Sarebbe interessante se potessi eseguire nuovamente i test delle prestazioni con questa variazione.Potrebbe essere il più veloce.

Modificare:Il modello sopra ha funzionato bene per me, ma alla fine ho cambiato per utilizzare le raccolte di Trove per ridurre le dimensioni della memoria in alcune mappe molto grandi che stavo creando - e come bonus era anche più veloce.

Una caratteristica davvero interessante è che il TObjectIntHashMap la classe ha un singolo adjustOrPutValue chiamata che, a seconda che sia già presente un valore in quella chiave, inserirà un valore iniziale o incrementerà il valore esistente.Questo è perfetto per incrementare:

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

HashMultiset delle raccolte Google:
- abbastanza elegante da usare
- ma consuma CPU e memoria

La cosa migliore sarebbe avere un metodo come: Entry<K,V> getOrPut(K); (elegante e low cost)

Tale metodo calcolerà l'hash e indice solo una volta, e quindi potremmo fare ciò che vogliamo con la voce (sostituire o aggiornare il valore).

Più elegante:
- prendi un HashSet<Entry>
- estenderlo in modo che get(K) inserire una nuova voce se necessario
- L'ingresso potrebbe essere il tuo oggetto.
--> (new MyHashSet()).get(k).increment();

"put" necessita di "get" (per garantire l'assenza di chiavi duplicate).
Quindi esegui direttamente un "put",
e se c'era un valore precedente, esegui un'addizione:

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
}

Se il conteggio inizia da 0, aggiungi 1:(o qualsiasi altro valore...)

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
}

Avviso : Questo codice non è thread-safe.Usalo per costruire e poi usare la mappa, non per aggiornarla contemporaneamente.

Ottimizzazione: In un ciclo, mantieni il vecchio valore per diventare il nuovo valore del ciclo successivo.

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
  }
}

I vari involucri primitivi, ad es. Integer sono immutabili, quindi non c'è davvero un modo più conciso per fare ciò che stai chiedendo salvo che puoi farlo con qualcosa del genere AtomicLong.Posso provarlo tra un minuto e aggiornare.A proposito, Tabella hash È una parte del Quadro delle collezioni.

Utilizzerei Apache Collections Lazy Map (per inizializzare i valori su 0) e utilizzerei MutableIntegers di Apache Lang come valori in quella mappa.

Il costo maggiore è dover cercare la mappa due volte nel tuo metodo.Nel mio devi farlo solo una volta.Basta ottenere il valore (verrà inizializzato se assente) e incrementarlo.

IL Java funzionale biblioteca TreeMap la struttura dati ha un update metodo nell'ultima testata del tronco:

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

Utilizzo di esempio:

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

Questo programma stampa "2".

@Vilmantas Baranauskas:Per quanto riguarda questa risposta, commenterei se avessi i punti rep, ma non li ho.Volevo notare che la classe Counter definita lì NON è thread-safe in quanto non è sufficiente sincronizzare semplicemente inc() senza sincronizzare value().Non è garantito che altri thread che chiamano value() visualizzino il valore a meno che non sia stata stabilita una relazione "accade prima" con l'aggiornamento.

Non so quanto sia efficiente, ma funziona anche il codice seguente. È necessario definire a BiFunction all'inizio.Inoltre, con questo metodo puoi fare molto più che un semplice incremento.

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

l'uscita è

3
1

Se stai usando Collezioni di Eclissi, puoi usare a HashBag.Sarà l'approccio più efficiente in termini di utilizzo della memoria e funzionerà bene anche in termini di velocità di esecuzione.

HashBag è supportato da a MutableObjectIntMap che memorizza gli interi primitivi invece di Counter oggetti.Ciò riduce il sovraccarico della memoria e migliora la velocità di esecuzione.

HashBag fornisce l'API di cui avresti bisogno poiché è un file Collection che consente anche di eseguire una query per il numero di occorrenze di un elemento.

Ecco un esempio da Collezioni 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"));

Nota: Sono un committente per le raccolte Eclipse.

Abbastanza semplice, basta usare la funzione integrata in Map.java come segue

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

Poiché molte persone cercano risposte Groovy negli argomenti Java, ecco come puoi farlo in 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}

Spero di aver compreso correttamente la tua domanda, vengo a Java da Python in modo da poter entrare in empatia con la tua lotta.

se hai

map.put(key, 1)

faresti

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

Spero che questo ti aiuti!

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top