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

OK, może to stare pytanie, ale z Javą 8 jest krótszy sposób:

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

Co robi: Jeśli Klucz nie istnieje, umieść 1 jako wartość, w przeciwnym razie suma 1 {[5] } do wartości powiązanej z kluczem . Więcej informacji tutaj

Małe badania w 2016 roku: https://github.com/leventov/java-word-count, benchmark source code

Najlepsze wyniki według metody (mniejsze jest lepsze):

                 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

Czas\przestrzeń wyniki:

@Hank Gay

Jako kontynuacja mojego (raczej bezużytecznego) komentarza: Jeśli z jakiegoś powodu chcesz trzymać się standardowego JDK, ConcurrentMapi AtomicLongmogą sprawić, że kod będzie tiny nieco ładniejszy, chociaż YMMV.

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

Pozostawi 1 jako wartość na mapie dla foo. Realistycznie, zwiększona przyjazność dla gwintowania to wszystko, co to podejście ma do polecania go.

GoogleGuava jest twoim przyjacielem...

Np.

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

Można również dodać więcej niż 1 do wartości:

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

Zawsze warto zajrzeć do Biblioteki zbiorów Google . W tym przypadku wystarczy Multiset :

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

Istnieją podobne do Map metody iteracji nad kluczami / wpisami itp. Wewnętrznie implementacja obecnie używa HashMap<E, AtomicInteger>, więc nie będziesz ponosił kosztów boksu.

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

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

Zawiera dwie potencjalnie kosztowne operacje na mapie, mianowicie containsKey i get. Ten pierwszy wykonuje operację potencjalnie podobną do tej drugiej, więc wykonujesz tę samą pracę dwa razy !

Jeśli spojrzysz na API Map, get operacje zwykle zwracają null, gdy mapa nie zawiera żądanego elementu.

Zauważ, że to sprawi, że rozwiązanie jak

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

Niebezpieczne, ponieważ może dać NullPointerException s. powinieneś najpierw sprawdzić, czy null.

zwróć również uwagę , a to jest bardzo ważne, że HashMap s Może zawierać nulls z definicji. Więc nie każdy zwracany null mówi "nie ma takiego elementu". Pod tym względem containsKeyzachowuje się inaczej od getw rzeczywistości mówiąc ci czy istnieje taki element. Szczegółowe informacje można znaleźć w API.

Dla Twojego case, jednak, możesz nie chcieć rozróżniać pomiędzy przechowywanym null i "noSuchElement". Jeśli nie chcesz pozwolić null s, Możesz wybrać Hashtable. Korzystanie z biblioteki wrapper, 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 uzupełnić odpowiedź (i zapomniałem umieścić to na początku, dzięki funkcji edycji!), najlepszym sposobem robienia tego natywnie jest get do zmiennej final , sprawdź, czy null i put jest z powrotem w 1. Zmienna powinna być final, ponieważ i tak jest niezmienna. Kompilator może nie potrzebować tej podpowiedzi, ale w ten sposób jest wyraźniejszy.

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

Jeśli nie chcesz polegać na autoboxingu, powinieneś zamiast tego powiedzieć coś w stylu map.put(new Integer(1 + i.getValue()));.

Innym sposobem byłoby stworzenie mutowalnej 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 do tworzenia liczby całkowitej (nawet z liczbą całkowitą.valueOf) nie powinno być tak dużo.

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

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

Korzyść:

• nie Tworzenie innej klasy dla mutable int
• Krótki kod
• łatwe do zrozumienia
• brak wyjątku wskaźnika null

Innym sposobem jest użycie metody merge, ale to zbyt wiele, aby po prostu zwiększyć wartość.

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

Sugestia: powinieneś dbać o czytelność kodu bardziej niż o niewielki wzrost wydajności przez większość czasu.

Rotacja Pamięci Może być tutaj problemem, ponieważ każdy Boks liczby int większej lub równej 128 powoduje alokację obiektów (Patrz liczba całkowita.valueOf(int)). Chociaż garbage collector bardzo skutecznie radzi sobie z krótkotrwałymi obiektami, wydajność ucierpi w pewnym stopniu.

Jeśli wiesz, że liczba dokonanych przyrostów znacznie przewyższa liczbę kluczy (=słowa w tym przypadku), rozważ użycie posiadacza int. Phax już przedstawił kod do tego. Znowu to samo., z dwiema zmianami (Klasa holder stała i 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 Map, która jest bezpośrednio dostosowana do prymitywnych typów wartości. jrudolph wspomniał GNU Trove .

Przy okazji, dobrym terminem wyszukiwania dla tego tematu jest "histogram".

Zamiast wywoływać containsKey (), szybsze jest wywołanie map.get i sprawdź, czy zwracana wartość jest null czy nie.

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

Możesz użyć metody computeIfAbsent w interfejsie Map dostarczonym w 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]

Metoda computeIfAbsent sprawdza czy podany klucz jest już skojarzony z wartością czy nie? Jeśli nie ma powiązanej wartości, to próbuje obliczyć jej wartość za pomocą podanej funkcji mapowania. W każdym przypadku zwraca bieżącą (istniejącą lub obliczoną) wartość powiązaną z podanym kluczem, lub null, jeśli obliczona wartość jest null.

Na marginesie, jeśli masz sytuację jeśli wiele wątków aktualizuje wspólną sumę, możesz spojrzeć na klasę LongAdder .W związku z dużą konkurencją, oczekiwana przepustowość tej klasy jest znacznie wyższa niż AtomicLong, kosztem większego zużycia przestrzeni.

Jesteś pewien, że to wąskie gardło? Zrobiłeś jakąś analizę wydajności?

Spróbuj użyć NetBeans profiler (jego bezpłatny i Wbudowany W NB 6.1), aby spojrzeć na hotspoty.

Wreszcie, aktualizacja JVM (powiedzmy od 1.5 - >1.6) jest często tanim wzmacniaczem wydajności. Nawet ulepszenie w liczbie kompilacji może zapewnić dobre zwiększenie wydajności. Jeśli używasz systemu Windows i jest to aplikacja klasy server, użyj -server w wierszu poleceń, aby użyć Hotspot serwera JVM. Na Linuksie i Solarisie Maszyny to jest wykrywane automatycznie.

Istnieje kilka podejść:

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

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

    class My{
        String word;
        int count;
    }

I użyj put("word", new My("Word")); następnie możesz sprawdzić, czy istnieje i zwiększyć przy dodawaniu.

Unikaj tworzenia własnych rozwiązań za pomocą list, ponieważ jeśli uzyskasz wyszukiwanie i sortowanie innerloop, twoja wydajność będzie śmierdzieć. Pierwszym rozwiązaniem HashMap jest właściwie dość szybko, ale odpowiedni taki znaleziony w kolekcjach Google jest chyba lepszy.

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

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

Używanie HashMultiset jest dość eleganckie, ponieważ algorytm worka jest właśnie tym, czego potrzebujesz przy liczeniu słów.

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

Możesz spojrzeć na GNU Trove . Jest to biblioteka, która zawiera wszelkiego rodzaju szybkie prymitywne zbiory. Twój przykład użyje TObjectIntHashMap, która ma metodę adjustOrPutValue, która robi dokładnie to, co chcesz.

Odmianą podejścia MutableInt, która może być jeszcze szybsza, jeśli trochę się włamać, jest użycie jednoelementowej tablicy int:

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ł powtórzyć testy wydajności z tą odmianą. Może być najszybszy.

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

Jeden naprawdę dobrą cechą jest to, że klasa TObjectIntHashMap ma jedno wywołanie adjustOrPutValue, które w zależności od tego, czy w tym kluczu jest już wartość, albo wprowadzi wartość początkową, albo zwiększy istniejącą wartość. To jest idealne do przyrostu:

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

Google Collections HashMultiset:
- dość elegancki w użyciu
- ale zużywają procesor i pamięć

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

Taka metoda będzie obliczać hash i indeks tylko raz, i wtedy możemy zrobić co chcemy z wpisem (zastąp lub zaktualizuj wartość).

Bardziej eleganckie:
- weź HashSet<Entry>
- rozszerz go tak, aby get(K) umieścić nowy wpis w razie potrzeby
- Wejście Może być twoim własnym obiektem.
--> (new MyHashSet()).get(k).increment();

" put "wymaga" get " (aby zapewnić brak duplikatu klucza).
Więc bezpośrednio zrób "put",
a jeśli była poprzednia wartość, to wykonaj dodanie:

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 count 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 do zbudowania, a następnie użyj mapy, a nie do jednoczesnej aktualizacji.

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

Różne prymitywne opakowania, np. Integer są niezmienne, więc nie ma bardziej zwięzłego sposobu na zrobienie tego, o co prosisz , chyba że możesz to zrobić za pomocą czegoś w rodzaju AtomicLong. Mogę spróbować za minutę i zaktualizować. BTW, Hashtable jest częścią struktury zbiorów .

Użyłbym Apache Collections Lazy Map (aby zainicjować wartości na 0) i użyć MutableIntegers z Apache Lang jako wartości w tej mapie.

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

Functional Java Library ' s TreeMap datastruktura ma metodę update w najnowszym nagłówku tułowia:

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 wyświetla "2".

@Vilmantas Baranauskas: jeśli chodzi o tę odpowiedź, skomentowałbym, gdybym miał punkty rep, ale nie mam. chciałem zauważyć, że zdefiniowana tam Klasa Counter nie jest bezpieczna dla wątku, ponieważ nie wystarczy tylko zsynchronizować inc() bez synchronizacji value(). Inne wątki wywołujące metodę value() nie mają gwarancji, że zobaczą wartość, chyba że zostanie ustanowiona relacja happens-before z aktualizacją.

Nie wiem, jak wydajny jest, ale poniższy kod również działa.Na początku musisz zdefiniować BiFunction. Plus, można zrobić więcej niż tylko przyrost z tej metody.

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 To

3
1

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

HashBag jest wspierany przez MutableObjectIntMap, który przechowuje prymitywne ints zamiast Counter obiektów. Zmniejsza to obciążenie pamięci i poprawia szybkość wykonania.

HashBag dostarcza API, którego potrzebujesz, ponieważ jest to Collection, który pozwala również zapytywać o liczbę wystąpień pozycji.

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

Notatka: jestem committerem Dla Kolekcji Eclipse.

Ponieważ wiele osób szuka Groovy odpowiedzi w tematach Javy, oto jak możesz 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}