putifabsent - key hashmap java



Il modo più efficiente per incrementare un valore di Map in Java (17)

Spero che questa domanda non sia considerata troppo semplice per questo forum, ma vedremo. Mi sto chiedendo come rifattorizzare qualche codice per ottenere prestazioni migliori che vengono eseguite più 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 contata e il valore è un numero intero che viene incrementato ogni volta che viene trovato un token della parola.

In Perl, incrementare 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, naturalmente, si basa sulla funzionalità di autoboxing nelle nuove versioni di Java. Mi chiedo se è possibile suggerire un modo più efficiente di incrementare tale valore. Ci sono anche buone ragioni per le prestazioni per evitare il framework Collections e usare invece qualcos'altro?

Aggiornamento: ho fatto un test di molte delle risposte. Vedi sotto.

https://src-bin.com


Answer #1

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 il più veloce. I cinque metodi che ho testato sono questi:

  • il metodo "ContainsKey" che ho presentato nella 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. creato cinque classi che erano identiche tranne per le differenze mostrate di seguito. Ogni classe doveva eseguire un'operazione tipica dello scenario presentato: aprire un file da 10 MB e leggerlo, quindi eseguire un conteggio di frequenza di tutti i token di parole nel file. Poiché ciò ha richiesto una media di soli 3 secondi, ho dovuto eseguire il conteggio delle frequenze (non l'I / O) per 10 volte.
  2. temporizzato il ciclo di 10 iterazioni ma non l'operazione di I / O e registrato il tempo totale impiegato (in secondi di orologio) utilizzando essenzialmente il metodo di Ian Darwin nel Cookbook di Java .
  3. ha eseguito tutti e cinque i test in serie, e poi l'ha fatto un altro tre volte.
  4. media dei quattro risultati per ciascun metodo.

risultati

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

Il metodo ContainsKey era, come previsto, il più lento, quindi darò la velocità di ciascun metodo rispetto alla velocità di quel metodo.

  • ContainsKey: 30.654 secondi (linea di base)
  • AtomicLong: 29.780 secondi (1,03 volte più veloce)
  • TestForNull: 28,804 secondi (1,06 volte più veloce)
  • Trove: 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 danno solo un incremento delle prestazioni superiore al 10%. Tuttavia, se il threading è un problema, AtomicLong potrebbe essere più attraente degli altri (non sono proprio sicuro). Ho anche eseguito TestForNull con variabili final , ma la differenza era trascurabile.

Si noti che non ho profilato l'utilizzo della memoria nei diversi scenari. Sarei felice di sentire da chiunque abbia una buona conoscenza di come i metodi MutableInt e Trove potrebbero influenzare l'utilizzo della memoria.

Personalmente, trovo il metodo MutableInt il più attraente, dal momento che non richiede il caricamento di classi di terze parti. Quindi, a meno che non scopro dei problemi, è il modo in cui sono più propenso ad andare.

Il codice

Ecco il codice cruciale di ciascun metodo.

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

Answer #2

Google Guava è tuo amico ...

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

Per esempio

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

Inoltre è possibile aggiungere più di 1 al valore:

map.getAndAdd(word, new Long(112)); 

Answer #3

È possibile utilizzare il metodo computeIfAbsent nell'interfaccia Map fornita in 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]

Il metodo computeIfAbsent verifica se la chiave specificata è già associata a un valore o no? Se nessun valore associato tenta di calcolare il suo valore utilizzando la funzione di mappatura fornita. In ogni caso restituisce il valore corrente (esistente o calcolato) associato alla chiave specificata, oppure null se il valore calcolato è nullo.

Una nota a LongAdder se si ha una situazione in cui più thread aggiornano una somma comune si può dare un'occhiata alla LongAdder di LongAdder Sotto alta contesa, il throughput previsto di questa classe è significativamente più alto di AtomicLong , a spese di un maggiore consumo di spazio.


Answer #4

È sempre una buona idea guardare la Biblioteca di Google Collections per questo genere di cose. In questo caso un Multiset 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 di tipo Map per iterare su chiavi / voci, ecc. Internamente, l'implementazione utilizza attualmente un HashMap<E, AtomicInteger> , quindi non dovrai sostenere costi di boxe.


Answer #5

@Hank Gay

Come follow-up del mio (piuttosto inutile) commento: Trove sembra la strada da percorrere. Se, per qualsiasi motivo, si desidera AtomicLong il JDK standard, ConcurrentMap e AtomicLong possono rendere il codice un po 'più bello, sebbene 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, l'aumento della cordialità nel threading è tutto ciò che questo approccio deve raccomandare.


Answer #6

Ci sono un paio di approcci:

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

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


    class My{
        String word;
        int count;
    }

E usa put ("word", new My ("Word")); Quindi puoi controllare se esiste e incrementare quando aggiungi.

Evita di far rotolare la tua soluzione usando gli elenchi, perché se ottieni ricerca interiore e ordinamento, le tue prestazioni faranno schifo. La prima soluzione di HashMap è in realtà abbastanza veloce, ma una versione corretta trovata in Google Collections è probabilmente migliore.

Contando le parole usando Google Collections, assomiglia a questo:



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


L'uso di HashMultiset è molto elegante, perché un algoritmo di borsa è proprio ciò di cui hai bisogno quando conti le parole.


Answer #7

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, ovvero containsKey e get . Il primo esegue un'operazione potenzialmente molto simile a quest'ultima, quindi stai facendo lo stesso lavoro due volte !

Se si guarda l'API per Map, le operazioni get solitamente restituiscono null quando la mappa non contiene l'elemento richiesto.

Si noti che questo renderà una soluzione simile

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

pericoloso, dal momento che potrebbe produrre NullPointerException s. Si dovrebbe prima verificare un null .

Nota anche , e questo è molto importante, che HashMap può contenere nulls per definizione. Quindi non ogni null restituito dice "non esiste un tale elemento". In questo senso, containsKey si comporta in modo diverso da get effettivamente in grado di dirti se c'è un tale elemento. Fare riferimento all'API per i dettagli.

Per il tuo caso, tuttavia, potresti non voler distinguere tra un null memorizzato e "noSuchElement". Se non vuoi consentire null s potresti preferire un Hashtable . L'utilizzo di una libreria wrapper come già proposto in altre risposte potrebbe rappresentare una soluzione migliore per il trattamento manuale, a seconda della complessità dell'applicazione.

Per completare la risposta (e ho dimenticato di inserirla all'inizio, grazie alla funzione di modifica!), Il modo migliore di farlo in modo nativo, è get in una variabile final , controllare null e put in una 1 . La variabile dovrebbe essere final perché è comunque immutabile. Il compilatore potrebbe non aver bisogno di questo suggerimento, ma è più chiaro in questo modo.

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 su autoboxing, dovresti dire qualcosa come map.put(new Integer(1 + i.getValue())); anziché.


Answer #8

HashMultiset Google Collections:
- abbastanza elegante da usare
- ma consumano CPU e memoria

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

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

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


Answer #9

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

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

Answer #10

La TreeMap dati TreeMap della libreria Java funzionale ha un metodo di update nell'ultima testa del trunk:

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

Esempio di utilizzo:

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


Answer #11

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

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'output è

3
1

Answer #12

OK, potrebbe essere una vecchia domanda, ma c'è un modo più breve con Java 8:

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

Che cosa fa: se la chiave non esiste, inserisci 1 come valore, altrimenti somma 1 al valore collegato alla chiave . Maggiori informazioni here


Answer #13

Se utilizzi raccolte Eclipse , puoi utilizzare un HashBag . Sarà l'approccio più efficiente in termini di utilizzo della memoria e sarà anche performante in termini di velocità di esecuzione.

HashBag è supportato da un oggetto MutableObjectIntMap che memorizza MutableObjectIntMap invece di oggetti Counter . Ciò riduce l'overhead della memoria e migliora la velocità di esecuzione.

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

Ecco un esempio delle 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 committer per le raccolte di Eclipse.


Answer #14

Sei sicuro che questo sia un collo di bottiglia? Hai fatto qualche analisi delle prestazioni?

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

Infine, un aggiornamento JVM (ad esempio da 1.5-> 1.6) è spesso un aumento di prestazioni a basso costo. Anche un aggiornamento del numero di build può fornire ottimi miglioramenti alle prestazioni. Se si esegue su Windows e questa è un'applicazione di classe server, utilizzare -server sulla riga di comando per utilizzare la JVM di Server Hotspot. Su macchine Linux e Solaris questo viene rilevato automaticamente.



Answer #16

Una variante dell'approccio MutableInt che potrebbe essere anche più veloce, se un po 'un hack, è usare 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 fosse possibile rieseguire i test delle prestazioni con questa variazione. Potrebbe essere il più veloce.

Edit: Il pattern sopra ha funzionato bene per me, ma alla fine ho cambiato le collezioni 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 la classe TObjectIntHashMap ha una singola chiamata adjustOrPutValue che, a seconda che esista già un valore su quella chiave, inserirà un valore iniziale o incrementerà il valore esistente. Questo è perfetto per l'incremento:

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

Answer #17
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 si incrementa un valore con un codice semplice.

Vantaggio:

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

Un altro modo è utilizzare il metodo di unione, ma questo è troppo per l'incremento di un valore.

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

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





collections