Najbardziej efektywny sposób na zwiększenie wartości mapy w Javie

377

Mam nadzieję, że to pytanie nie jest uważane za zbyt podstawowe dla tego forum, ale zobaczymy. Zastanawiam się, jak refaktoryzować kod, aby uzyskać lepszą wydajność, która jest uruchamiana kilka razy.

Załóżmy, że tworzę listę częstotliwości słów, korzystając z mapy (prawdopodobnie HashMap), w której każdy klucz jest ciągiem ze słowem, które jest zliczane, a wartością jest liczba całkowita, która jest zwiększana za każdym razem, gdy zostanie znaleziony token słowa.

W Perlu zwiększenie takiej wartości byłoby banalnie proste:

$map{$word}++;

Ale w Javie jest to o wiele bardziej skomplikowane. Oto sposób, w jaki obecnie to robię:

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

Co oczywiście zależy od funkcji autoboxowania w nowszych wersjach Java. Zastanawiam się, czy możesz zasugerować bardziej skuteczny sposób na zwiększenie takiej wartości. Czy istnieją nawet dobre powody, dla których warto unikać ramek Kolekcje i używać czegoś innego?

Aktualizacja: Zrobiłem test kilku odpowiedzi. Patrz poniżej.

Gregory
źródło
Myślę, że byłoby tak samo dla java.util.Hashtable.
jrudolph
2
Oczywiście, jeśli byłoby tak samo, ponieważ Hashtable ma wpływ na mapę.
whiskeysierra
Java 8: przykład computeIfAbsent: stackoverflow.com/a/37439971/1216775
akhil_mittal

Odpowiedzi:

366

Niektóre wyniki testu

Otrzymałem wiele dobrych odpowiedzi na to pytanie - dzięki, ludzie - więc postanowiłem przeprowadzić kilka testów i dowiedzieć się, która metoda jest rzeczywiście najszybsza. Pięć metod, które przetestowałem, to:

  • metoda „ContainsKey”, którą przedstawiłem w pytaniu
  • metoda „TestForNull” sugerowana przez Aleksandra Dymitrowa
  • metoda „AtomicLong” sugerowana przez Hanka Gaya
  • metoda „Trove” sugerowana przez jrudolpha
  • metoda „MutableInt” sugerowana przez phax.myopenid.com

metoda

Oto co zrobiłem ...

  1. utworzono pięć klas, które były identyczne, z wyjątkiem różnic pokazanych poniżej. Każda klasa musiała wykonać operację typową dla przedstawionego przeze mnie scenariusza: otworzyć plik 10 MB i wczytać go, a następnie wykonać liczenie częstotliwości wszystkich tokenów słów w pliku. Ponieważ zajęło to średnio tylko 3 sekundy, kazałem mu wykonać liczenie częstotliwości (nie I / O) 10 razy.
  2. dokonał pomiaru pętli 10 iteracji, ale nie operacji I / O i zarejestrował całkowity czas (w sekundach zegarowych) zasadniczo przy użyciu metody Iana Darwina w książce kucharskiej Java .
  3. wykonał wszystkie pięć testów w szeregu, a następnie zrobił to jeszcze trzy razy.
  4. uśredniono cztery wyniki dla każdej metody.

Wyniki

Najpierw przedstawię wyniki, a poniżej kod dla zainteresowanych.

Metoda ContainsKey była, zgodnie z oczekiwaniami, najwolniejsza, dlatego podam prędkość każdej metody w porównaniu do prędkości tej metody.

  • Zawiera klucz : 30,654 sekundy (linia bazowa)
  • AtomicLong: 29,780 sekund (1,03 razy szybciej)
  • TestForNull: 28,804 sekundy (1,06 razy szybciej)
  • Trove: 26,313 sekund (1,16 razy szybciej)
  • MutableInt: 25,747 sekund (1,19 razy szybciej)

Wnioski

Wydaje się, że tylko metoda MutableInt i metoda Trove są znacznie szybsze, ponieważ tylko one dają wzrost wydajności o ponad 10%. Jeśli jednak wątek stanowi problem, AtomicLong może być bardziej atrakcyjny niż inne (nie jestem do końca pewien). Uruchomiłem także TestForNull ze finalzmiennymi, ale różnica była znikoma.

Pamiętaj, że nie profilowałem użycia pamięci w różnych scenariuszach. Z przyjemnością dowiem się od każdego, kto ma dobry wgląd w to, w jaki sposób metody MutableInt i Trove mogłyby wpłynąć na wykorzystanie pamięci.

Osobiście uważam, że metoda MutableInt jest najbardziej atrakcyjna, ponieważ nie wymaga ładowania żadnych klas stron trzecich. Więc jeśli nie odkryję problemów z tym, najprawdopodobniej pójdę.

Kod

Oto kluczowy kod z każdej metody.

Zawiera klucz

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
źródło
3
Świetna robota, dobra robota. Drobny komentarz - wywołanie putIfAbsent () w kodzie AtomicLong utworzy nową instancję AtomicLong (0), nawet jeśli jest już na mapie. Jeśli poprawisz to, aby użyć if (map.get (key) == null), prawdopodobnie uzyskasz poprawę wyników testów.
Leigh Caldwell,
2
Ostatnio zrobiłem to samo z podejściem podobnym do MutableInt. Cieszę się, że było to optymalne rozwiązanie (po prostu założyłem, że nie było żadnych testów).
Kip
Miło słyszeć, że jesteś szybszy ode mnie, Kip. ;-) Daj mi znać, jeśli odkryjesz jakieś wady tego podejścia.
gregory
4
W przypadku Atomic Long nie byłoby bardziej efektywne zrobić to w jednym kroku (więc masz tylko 1 kosztowną operację get zamiast 2) „map.putIfAbsent (word, new AtomicLong (0)). IncrementAndGet ();”
smartnut007
1
@gregory, czy zastanawiałeś się nad Javą 8 freq.compute(word, (key, count) -> count == null ? 1 : count + 1)? Wewnętrznie robi to o jeden mniej zaszyfrowany przegląd niż containsKey, byłoby interesujące zobaczyć, jak wypada w porównaniu z innymi, z powodu lambda.
TWiStErRob
255

Teraz jest krótszy sposób korzystania z Java 8 Map::merge.

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

Co to robi:

  • jeśli klucz nie istnieje, wpisz 1 jako wartość
  • w przeciwnym razie sumuje 1 do wartości powiązanej z kluczem

Więcej informacji tutaj .

LE GALL Benoît
źródło
zawsze kocham java 8. Czy to jest atomowe? czy powinienem go zsynchronizować?
Tiina,
4
To nie wydają się działać dla mnie, ale map.merge(key, 1, (a, b) -> a + b); nie
russter
2
@ Tiina Charakterystyka atomowości jest specyficzna dla implementacji, por. the docs : „Domyślna implementacja nie daje żadnych gwarancji dotyczących synchronizacji ani właściwości atomowości tej metody. Każda implementacja zapewniająca gwarancje atomowości musi zastąpić tę metodę i udokumentować jej właściwości współbieżności. W szczególności wszystkie implementacje podinterface ConcurrentMap muszą udokumentować, czy funkcja jest zastosowana raz atomowo tylko wtedy, gdy wartość nie jest obecna. ”
jensgram
2
Dla groovy, nie zaakceptuje Integer::sumjako BiFunkcji i nie podoba się @russter odpowiedzieć w sposób, w jaki został napisany. To zadziałało dla mnieMap.merge(key, 1, { a, b -> a + b})
jookyone
2
@russter, wiem, że twój komentarz był ponad rok temu, ale czy pamiętasz, dlaczego to nie zadziałało? Wystąpił błąd kompilacji lub nie wartość została zwiększona?
Paul
44

Trochę badań w 2016 r .: https://github.com/leventov/java-word-count , kod źródłowy testu porównawczego

Najlepsze wyniki na metodę (im mniejsza, tym lepsza):

                 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

Wyniki dla czasu \ przestrzeni:

lewentow
źródło
2
Dzięki, to było naprawdę pomocne. Byłoby fajnie dodać Multiset Guavy (na przykład HashMultiset) do testu porównawczego.
cabad
34

Google Guava jest twoim przyjacielem ...

... przynajmniej w niektórych przypadkach. Mają fajną AtomicLongMap . Szczególnie miłe, bo masz do czynienia z długo jak wartość w mapie.

Na przykład

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

Możliwe jest również dodanie do wartości więcej niż 1:

map.getAndAdd(word, 112L); 
H6
źródło
7
AtomicLongMap#getAndAddprzyjmuje prymitywną, longa nie klasę opakowania; nie ma sensu tego robić new Long(). I AtomicLongMapjest sparametryzowanym typem; powinieneś był to zadeklarować AtomicLongMap<String>.
Helder Pereira
32

@Hank Gay

Jako kontynuacja mojego (raczej bezużytecznego) komentarza: Trove wygląda jak droga. Jeżeli z jakiegoś powodu chcesz trzymać się standardowego JDK, ConcurrentMap i AtomicLong może sprawić, że kodują malutki nieco ładniejszy, chociaż YMMV.

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

pozostawi 1jako wartość na mapie dla foo. Realistycznie, zwiększona łatwość nawlekania wątków to wszystko, co takie podejście musi polecić.

Hank Gay
źródło
9
Metoda putIfAbsent () zwraca wartość. Dużym ulepszeniem może być przechowywanie zwracanej wartości w zmiennej lokalnej i używanie jej do incrementAndGet (), a nie do wywołania get ponownie.
smartnut007,
putIfAbsent może zwrócić wartość null, jeśli określony klucz nie jest już powiązany z wartością w Mapie, więc ostrożnie skorzystam ze zwróconej wartości. 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);

I w ten sposób zwiększasz wartość za pomocą prostego kodu.

Zasiłek:

  • Nie trzeba dodawać nowej klasy ani używać innej koncepcji mutable int
  • Nie poleganie na żadnej bibliotece
  • Łatwo zrozumieć, co dokładnie się dzieje (niezbyt abstrakcja)

Minusem:

  • Mapa hash zostanie dwukrotnie przeszukana pod kątem get () i put (). Więc nie będzie to najbardziej wydajny kod.

Teoretycznie po wywołaniu get () wiesz już, gdzie umieścić (), więc nie powinieneś ponownie szukać. Ale wyszukiwanie mapy skrótów zajmuje zwykle bardzo minimalny czas, który można zignorować ten problem z wydajnością.

Ale jeśli poważnie podchodzisz do problemu, jesteś perfekcjonistą, innym sposobem jest użycie metody scalania, jest to (prawdopodobnie) bardziej wydajne niż poprzedni fragment kodu, ponieważ (teoretycznie) przeszukujesz mapę tylko raz: (chociaż ten kod nie jest oczywisty od pierwszego wejrzenia, jest krótki i wydajny)

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

Sugestia: przez większość czasu powinieneś dbać o czytelność kodu, a nie o niewielki wzrost wydajności. Jeśli łatwiej jest zrozumieć pierwszy fragment kodu, użyj go. Ale jeśli jesteś w stanie zrozumieć drugą grzywnę, możesz też ją wybrać!

off99555
źródło
Metoda getOfDefault nie jest dostępna w JAVA 7. Jak mogę to osiągnąć w JAVA 7?
tanvi
1
Być może będziesz musiał polegać na innych odpowiedziach. Działa to tylko w Javie 8.
off99555
1
+1 dla rozwiązania scalającego, będzie to funkcja o najwyższej wydajności, ponieważ musisz zapłacić tylko 1 raz za obliczenie kodu skrótu (w przypadku, gdy mapa, na której używasz go poprawnie obsługuje metodę), zamiast potencjalnie płacić za to 3 razy
Ferrybig
2
Metoda wnioskowania: map.merge (key, 1, Integer :: sum)
earandap
25

Zawsze warto poszukać czegoś takiego w Bibliotece kolekcji Google . W takim przypadku Multiset wykona lewę:

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

Istnieją metody przypominające mapę do iteracji kluczy / wpisów itp. Wewnętrznie implementacja obecnie używa a HashMap<E, AtomicInteger>, więc nie poniesiesz kosztów boksu.

Chris Nokleberg
źródło
Powyższy automatyczna sekretarka musi odzwierciedlać odpowiedź odmienną. Interfejs API zmienił się od czasu opublikowania (3 lata temu :))
Steve,
Czy count()metoda na wielu zestawach działa w czasie O (1) lub O (n) (w najgorszym przypadku)? Dokumenty nie są jasne w tej kwestii.
Adam Parkin
Mój algorytm do tego rodzaju rzeczy: if (hasApacheLib (rzecz)) zwraca apacheLib; w przeciwnym razie, jeśli (hasOnGuava (rzecz)) zwróci guawa. Zazwyczaj nie przechodzę przez te dwa kroki. :)
digao_mb
22

Powinieneś być świadomy faktu, że Twoja pierwotna próba

liczba int = map.containsKey (słowo)? map.get (słowo): 0;

zawiera dwie potencjalnie drogie operacje na mapie, a mianowicie containsKeyi get. Pierwsza wykonuje operację potencjalnie podobną do drugiej, więc wykonuje się tę samą pracę dwa razy !

Jeśli spojrzysz na API dla mapy, getoperacje zwykle powracająnull gdy mapa nie zawiera żądanego elementu.

Zauważ, że dzięki temu rozwiążesz takie rozwiązanie

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

niebezpieczne, ponieważ może dać NullPointerExceptions. Powinieneś nullnajpierw sprawdzić .

Należy również pamiętać , a to jest bardzo ważne, że HashMapów może zawierać nullsdefinicji. Więc nie każdy wrócił nullmówi „nie ma takiego elementu”. Pod tym względem containsKeyzachowuje się inaczej niż getw rzeczywistości mówiąc, czy istnieje taki element. Szczegółowe informacje można znaleźć w interfejsie API.

Jednak w twoim przypadku możesz nie chcieć rozróżniać między przechowywanym nulla „noSuchElement”. Jeśli nie chcesz zezwalać, nullmożesz preferowaćHashtable . Korzystanie z biblioteki opakowań, jak już zaproponowano w innych odpowiedziach, może być lepszym rozwiązaniem do ręcznego leczenia, w zależności od złożoności aplikacji.

Aby ukończyć odpowiedź (i zapomniałem na początku to wstawić, dzięki funkcji edycji!), Najlepszym sposobem na zrobienie tego natywnie, jest getprzejście do finalzmiennej, sprawdzenie nulli ponowne sprawdzenie za putpomocą 1. Zmienna powinna być, finalponieważ i tak jest niezmienna. Kompilator może nie potrzebować tej wskazówki, ale w ten sposób jest jaśniejszy.

końcowa mapa HashMap = generateRandomHashMap ();
final Object key = fetchSomeKey ();
końcowa liczba całkowita i = map.get (klucz);
jeśli (i! = null) {
    map.put (i + 1);
} else {
    // Zrób coś
}

Jeśli nie chcesz polegać na autoboxowaniu, powinieneś powiedzieć coś takiego map.put(new Integer(1 + i.getValue()));.

Aleksandar Dimitrov
źródło
Aby uniknąć problemu początkowych niezmapowanych / zerowych wartości w groovy, kończę na: counts.put (key, (counts.get (key)?: 0) + 1) // nadmiernie złożona wersja ++
Joe Atzberger
2
Lub najprościej: counts = [:]. WithDefault {0} // ++ away
Joe Atzberger
18

Innym sposobem byłoby utworzenie zmiennej liczby całkowitej:

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

oczywiście oznacza to utworzenie dodatkowego obiektu, ale narzut w porównaniu z tworzeniem liczby całkowitej (nawet z Integer.valueOf) nie powinien być aż tak duży.

Philip Helger
źródło
5
Nie chcesz uruchomić MutableInt od 1, kiedy umieścisz ją na mapie?
Tom Hawtin - tackline
5
Commons-lang Apache'a ma już dla ciebie MutableInt.
SingleShot,
11

Możesz skorzystać z metody computeIfAbsent w Mapinterfejsie udostępnionym w Javie 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]

Metoda computeIfAbsentsprawdza, czy określony klucz jest już powiązany z wartością, czy nie? Jeśli nie ma powiązanej wartości, wówczas próbuje obliczyć swoją wartość przy użyciu danej funkcji odwzorowania. W każdym przypadku zwraca bieżącą (istniejącą lub obliczoną) wartość powiązaną z określonym kluczem lub null, jeśli obliczona wartość jest null.

Na marginesie, jeśli masz sytuację, w której wiele wątków aktualizuje wspólną sumę, możesz spojrzeć na klasę LongAdder. Przy dużej rywalizacji oczekiwana przepustowość tej klasy jest znacznie wyższa niż AtomicLongkosztem większego zużycia miejsca.

akhil_mittal
źródło
dlaczego concurrentHashmap i AtomicLong?
ealeon
7

Problemem może być rotacja pamięci, ponieważ każde boksowanie liczby całkowitej większej lub równej 128 powoduje przydział obiektu (patrz Integer.valueOf (int)). Chociaż moduł wyrzucania śmieci bardzo skutecznie radzi sobie z obiektami krótkotrwałymi, wydajność do pewnego stopnia ucierpi.

Jeśli wiesz, że liczba dokonanych przyrostów znacznie przewyższy liczbę kluczy (= w tym przypadku słów), rozważ użycie int int. Phax już przedstawił kod do tego. Oto znowu, z dwiema zmianami (klasa posiadacza stała się statyczna, a wartość początkowa ustawiona na 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();
}

Jeśli potrzebujesz ekstremalnej wydajności, poszukaj implementacji mapy, która jest bezpośrednio dostosowana do pierwotnych typów wartości. jrudolph wspomniał o GNU Trove .

Nawiasem mówiąc, dobrym wyszukiwanym terminem dla tego tematu jest „histogram”.

salwa
źródło
5

Zamiast wywoływać metodę includeKey (), szybciej jest wywołać map.get i sprawdzić, czy zwracana wartość jest pusta, czy nie.

    Integer count = map.get(word);
    if(count == null){
        count = 0;
    }
    map.put(word, count + 1);
Glever
źródło
3

Czy na pewno jest to wąskie gardło? Czy przeprowadziłeś jakąś analizę wydajności?

Spróbuj użyć profilera NetBeans (darmowego i wbudowanego w NB 6.1), aby spojrzeć na hotspoty.

Wreszcie, aktualizacja JVM (powiedzmy z 1.5-> 1.6) jest często tanim wzmacniaczem wydajności. Nawet aktualizacja numeru kompilacji może zapewnić dobre zwiększenie wydajności. Jeśli korzystasz z systemu Windows i jest to aplikacja klasy serwera, użyj -server w wierszu polecenia, aby użyć JVM serwera Hotspot. W maszynach z systemem Linux i Solaris jest to wykrywane automatycznie.


źródło
3

Istnieje kilka podejść:

  1. Użyj alorithm Bag, jak zestawy zawarte w kolekcjach Google.

  2. Utwórz zmienny pojemnik, którego możesz użyć na mapie:


    class My{
        String word;
        int count;
    }

I użyj put („słowo”, nowe Moje („Słowo”)); Następnie możesz sprawdzić, czy istnieje i zwiększyć wartość podczas dodawania.

Unikaj rzucania własnym rozwiązaniem za pomocą list, ponieważ jeśli pojawi się wyszukiwanie i sortowanie w pętli wewnętrznej, wydajność będzie śmierdzieć. Pierwsze rozwiązanie HashMap jest w rzeczywistości dość szybkie, ale poprawne jest takie samo, jak w kolekcjach Google.

Liczenie słów za pomocą Kolekcji Google wygląda mniej więcej tak:



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


Korzystanie z HashMultiset jest dość eleganckie, ponieważ algorytm workowy jest właśnie tym, czego potrzebujesz do liczenia słów.

tovare
źródło
3

Myślę, że twoje rozwiązanie byłoby standardowe, ale - jak sam zauważyłeś - prawdopodobnie nie jest to najszybszy możliwy sposób.

Możesz spojrzeć na GNU Trove . Jest to biblioteka zawierająca wszelkiego rodzaju szybkie prymitywne kolekcje. Twój przykład użyłby TObjectIntHashMap, który ma metodę adjustOrPutValue, która robi dokładnie to, co chcesz.

jrudolph
źródło
Link do TObjectIntHashMap jest uszkodzony. To jest poprawny link: trove4j.sourceforge.net/javadocs/gnu/trove/map/…
Erel Segal-Halevi
Dzięki, Erel, naprawiłem link.
jrudolph,
3

Odmianą podejścia MutableInt, które może być jeszcze szybsze, jeśli jest trochę włamaniem, jest użycie tablicy intelementowej z jednym elementem:

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

Byłoby interesujące, gdybyś mógł ponownie uruchomić testy wydajności z tą odmianą. To może być najszybsze.


Edycja: Powyższy wzór działał dla mnie dobrze, ale ostatecznie zmieniłem użycie kolekcji Trove, aby zmniejszyć rozmiar pamięci na niektórych bardzo dużych mapach, które tworzyłem - i jako bonus było również szybsze.

Jedną naprawdę fajną cechą jest to, że TObjectIntHashMapklasa ma pojedyncze adjustOrPutValuewywołanie, które w zależności od tego, czy wartość ma już ten klucz, albo wprowadzi wartość początkową, albo zwiększy istniejącą wartość. Jest to idealne rozwiązanie do zwiększania:

TObjectIntHashMap<String> map = new TObjectIntHashMap<String>();
...
map.adjustOrPutValue(key, 1, 1);
Eamonn O'Brien-Strain
źródło
3

Kolekcje Google HashMultiset:
- dość elegancki w użyciu
- ale zużywa procesor i pamięć

Najlepiej byłoby mieć taką metodę jak: Entry<K,V> getOrPut(K); (elegancki i tani)

Taka metoda oblicza skrót i indeks tylko raz, a następnie moglibyśmy zrobić to, co chcemy z wpisem (zastąpić lub zaktualizować wartość).

Bardziej elegancki:
- weź HashSet<Entry>
- przedłuż go, aby get(K)w razie potrzeby wstawić nowy wpis
- wpis może być twoim własnym obiektem.
->(new MyHashSet()).get(k).increment();

Felis Leo
źródło
3

Po prostu użyj wbudowanej funkcji w Map.javanastępujący sposób

map.put(key, map.getOrDefault(key, 0) + 1);
sudoz
źródło
Nie zwiększa to wartości, ustawia tylko bieżącą wartość lub 0, jeśli do klawisza nie została przypisana żadna wartość.
siegi
Możesz zwiększyć wartość o ++... OMG, to takie proste. @siegi
sudoz
Dla przypomnienia: ++w tym wyrażeniu nie działa nigdzie, ponieważ zmienna jest potrzebna jako argument, ale są tylko wartości. Twój dodatek + 1działa. Teraz twoje rozwiązanie jest takie samo jak w odpowiedzi off99555 .
siegi
2

„put” need „get” (aby zapewnić brak duplikatu klucza).
Więc bezpośrednio zrób „put”,
a jeśli była poprzednia wartość, to dodaj:

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
}

Jeśli liczenie zaczyna się od 0, dodaj 1: (lub dowolne inne wartości ...)

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
}

Uwaga: ten kod nie jest bezpieczny dla wątków. Użyj go, aby zbudować, a następnie użyj mapy, a nie jej jednocześnie aktualizować.

Optymalizacja: w pętli zachowaj starą wartość, aby stała się nową wartością następnej pętli.

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
  }
}
Felis Leo
źródło
1

Różne prymitywne opakowania, na przykład, Integersą niezmienne, więc naprawdę nie ma bardziej zwięzłego sposobu robienia tego, o co prosisz, chyba że możesz to zrobić za pomocą czegoś takiego jak AtomicLong . Mogę spróbować za chwilę i zaktualizować. BTW, Hashtable jest częścią kolekcji Framework .

Hank Gay
źródło
1

Użyłbym Leniwej mapy kolekcji Apache (aby zainicjować wartości do 0) i użyłem MutableIntegers z Apache Lang jako wartości na tej mapie.

Największym kosztem jest dwukrotne przeszukanie mapy w twojej metodzie. W moim musisz to zrobić tylko raz. Po prostu pobierz wartość (zostanie zainicjowana, jeśli jej nie ma) i zwiększ ją.

jb.
źródło
1

Struktura danych biblioteki Functional JavaTreeMap zawiera updatemetodę w najnowszym nagłówku trunk:

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

Przykładowe użycie:

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

Ten program wypisuje „2”.

Apokalipsa
źródło
1

@Vilmantas Baranauskas: Jeśli chodzi o tę odpowiedź, chciałbym skomentować, gdybym miał punkty rep, ale nie mam. Chciałem zauważyć, że zdefiniowana tam klasa Counter NIE jest bezpieczna dla wątków, ponieważ nie wystarczy synchronizacja inc () bez synchronizacji wartości (). Inne wątki wywołujące wartość () nie mają gwarancji, że zobaczą tę wartość, chyba że zostanie ustanowiony związek przed aktualizacją.

Alex Miller
źródło
Jeśli chcesz odwołać się do czyjejś odpowiedzi, użyj @ [Nazwa użytkownika] u góry, np. @Vilmantas Baranauskas <Treść idzie tutaj>
Hank Gay
Dokonałem tej modyfikacji, aby ją oczyścić.
Alex Miller
1

Nie wiem, jak to jest wydajne, ale działa również poniższy kod. Musisz zdefiniować BiFunctionna początku. Co więcej, dzięki tej metodzie możesz zrobić coś więcej niż tylko przyrost.

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

wyjście jest

3
1
MGoksu
źródło
1

Jeśli używasz kolekcji Eclipse , możesz użyć HashBag. Będzie to najbardziej wydajne podejście pod względem wykorzystania pamięci, a także będzie dobrze działać pod względem szybkości wykonywania.

HashBagjest wspierany przez, MutableObjectIntMapktóry przechowuje prymitywne ints zamiast Counterobiektów. Zmniejsza to obciążenie pamięci i poprawia szybkość wykonywania.

HashBag zapewnia interfejs API, którego potrzebujesz, ponieważ jest to Collection umożliwia on również sprawdzenie liczby wystąpień elementu.

Oto przykład z 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"));

Uwaga: jestem osobą odpowiedzialną za kolekcje Eclipse.

Craig P. Motlin
źródło
1

Sugeruję użycie Java 8 Map :: compute (). Rozważa również przypadek, gdy klucz nie istnieje.

Map.compute(num, (k, v) -> (v == null) ? 1 : v + 1);
Eugene Chung
źródło
mymap.merge(key, 1, Integer::sum)?
Det
-2

Ponieważ wiele osób szuka w języku Java odpowiedzi na Groovy, oto jak to zrobić w 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
źródło
-2

Prosty i łatwy sposób w java 8 jest następujący:

final ConcurrentMap<String, AtomicLong> map = new ConcurrentHashMap<String, AtomicLong>();
    map.computeIfAbsent("foo", key -> new AtomicLong(0)).incrementAndGet();
Assaduzzaman Assad
źródło
-3

Mam nadzieję, że rozumiem twoje pytanie poprawnie, idę do Javy z Pythona, aby móc wczuć się w twoją walkę.

Jeśli masz

map.put(key, 1)

ty byś zrobił

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

Mam nadzieję że to pomoże!

ggaugler
źródło