Java에서 Map 값을 증가시키는 가장 효율적인 방법

OK, 오래된 질문 일지 모르지만 Java 8에서는 더 짧은 방법이 있습니다.

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

그것이하는 일 : if key 가 존재하지 않는다면, 1 을 value 그렇지 않으면 합계 1 을 키 에 연결된 값으로 변경하십시오. 추가 정보 여기

2016 년에 약간 연구 : https://github.com/leventov/Java-Word-count , 벤치 마크 소스 코드

방법 당 가장 좋은 결과 (작을수록 좋습니다) :

                 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

시간\공간 결과 : 

Google 구아바 당신의 친구입니다 ...

적어도 어떤 경우에는. 그들에게는 Nice AtomicLongMap 가 있습니다. 특히 Nice long 을 맵의 값으로 사용하기 때문에 좋습니다.

예 :.

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

또한 값에 1을 더 추가 할 수 있습니다.

map.getAndAdd(Word, 112L); 

@ 행크 게이

내 자신의 (오히려 쓸데없는) 코멘트에 대한 후속 조치로서 : Trove는 갈 길이 멀어 보인다. 어떤 이유로 든 표준 JDK를 고수하고 싶다면 ConcurrentMap 및 AtomicLong 는 코드를 작게 만들 수 있습니다. YMMV가 더 좋았습니다.

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

foo에 대한 맵의 값으로 1를 남겨 둡니다. 현실적으로 스레딩에 대한 친숙 함이 높아지면이 접근 방식이 권장할만한 것입니다.

이런 종류의 일에 대해 Google Collections Library 를 보면 항상 좋은 생각입니다. 이 경우 Multiset 트릭을 수행합니다.

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

키/엔트리 등을 반복하는 Map-like 메소드가 있습니다. 내부적으로 구현은 현재 HashMap<E, AtomicInteger>를 사용하므로 복싱 비용이 발생하지 않습니다.

원래의 시도가 있다는 사실을 알고 있어야합니다.

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

containsKey 및 get과 같이지도에 잠재적으로 값 비싼 두 가지 작업이 포함되어 있습니다. 전자는 잠재적으로 후자와 매우 유사한 작업을 수행하므로 동일한 작업을 수행합니다. 두 번!

Map 용 API를 보면 get 연산은 요청 된 요소가지도에없는 경우 null을 반환합니다.

이것은 다음과 같은 해결책을 만들 것임을 주목하십시오.

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

NullPointerExceptions를 산출 할 수 있기 때문에 위험합니다. 먼저 null을 확인해야합니다.

참고 사항, 그리고 이것은 매우 중요합니다. HashMaps can 정의에 따라 nulls을 포함합니다. 그래서 모든 반환 된 null은 "그와 같은 요소가 없습니다"라고 말하지 않습니다. 이 관점에서 containsKey은 다르게 ~ get에서 실제로 당신에게 == 그런 요소가 있음을 나타냅니다. 자세한 내용은 API를 참조하십시오.

그러나 귀하의 경우에는 저장된 null과 "noSuchElement"를 구분하고 싶지 않을 수 있습니다. null을 허용하지 않으려면 Hashtable을 선호 할 수 있습니다. 다른 응답에서 이미 제안 된 래퍼 라이브러리를 사용하면 응용 프로그램의 복잡도에 따라 수동 치료에 더 나은 솔루션이 될 수 있습니다.

해답을 완성하기 위해 (편집 기능 덕분에!), 네이티브로하는 가장 좋은 방법은 get 변수에 final 변수를 넣고 null 및 put 변수를 확인하고 1 . 변수는 어쨌든 불변이므로 final이어야합니다. 컴파일러는이 힌트를 필요로하지 않을 수도 있지만, 그렇게 명확하다.

 최종 정수형 i = map.get (key); 
 if (i. ! = null) {
 map.put (i + 1); 
} else {
 // 무언가 
} 

Autoboxing에 의존하고 싶지 않다면, 대신 map.put(new Integer(1 + i.getValue()));과 같은 것을 말해야합니다.

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

이것이 바로 간단한 코드로 값을 증가시키는 방법입니다.

이익:

• 변경 가능한 int에 대해 다른 클래스를 만들지 않습니다.
• 짧은 코드
• 이해하기 쉬운
• 널 포인터 예외 없음

또 다른 방법은 병합 메서드를 사용하는 것입니다. 그러나 이것은 단순히 값을 증가시키는 데 너무 많은 것입니다.

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

제안 : 코드 가독성은 대부분의 경우 거의 성능 향상보다 중요합니다.

또 다른 방법은 변경 가능한 정수를 만드는 것입니다.

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

물론 이것은 추가 객체를 만드는 것을 의미하지만 Integer.valueOf를 사용하는 경우에도 Integer를 만드는 것과 비교할 때 발생하는 오버 헤드는 그렇게 많이해서는 안됩니다.

Java Java 8 에서 제공되는 Map 인터페이스에서 computeIfAbsent 메소드를 사용할 수 있습니다.

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]

computeIfAbsent 메소드는 지정된 키가 이미 값과 연관되어 있는지 확인합니다. 관련 지을 수 있었던 값이없는 경우, 지정된 매핑 함수를 사용해 값을 계산하려고합니다. 어쨌든 지정된 키와 연관된 현재 (기존 또는 계산 된) 값을 반환하거나 계산 된 값이 null이면 null을 반환합니다.

부수적으로, 여러 스레드가 공통적 인 합계를 업데이트하는 상황이 발생하면 LongAdder 클래스를 볼 수 있습니다. 높은 경쟁으로 인해이 클래스의 예상 처리량은 비용으로 AtomicLong보다 상당히 높습니다. 더 많은 공간을 소비합니다.

128보다 크거나 같은 int의 모든 복싱이 객체 할당을 발생시키기 때문에 메모리 회전이 여기에서 문제가 될 수 있습니다 (Integer.valueOf (int) 참조). 가비지 컬렉터는 수명이 짧은 오브젝트를 매우 효율적으로 처리하지만 성능은 어느 정도 저하됩니다.

증가 된 숫자가 키의 수 (이 경우 단어 수)를 크게 상회하는 경우, 대신 int 홀더를 사용하는 것이 좋습니다. Phax는 이미이를위한 코드를 제시했습니다. 여기에 다시 두 가지 변경 사항이 있습니다 (홀더 클래스는 정적 및 초기 값을 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();
}

극단적 인 성능이 필요한 경우 기본 값 유형에 맞게 직접 조정 된 Map 구현을 찾으십시오. jrudolph 언급 GNU Trove .

그런데이 주제에 대한 좋은 검색어는 "히스토그램"입니다.

ContainsKey ()를 호출하는 대신 map.get을 호출하고 반환 된 값이 null인지 아닌지 확인하는 것이 빠릅니다.

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

몇 가지 접근법이 있습니다.

1. Google Collections에 포함 된 세트와 같은 Bag alorithm을 사용하십시오.

2. 지도에서 사용할 수있는 변경 가능한 컨테이너 만들기 :

    class My{
        String Word;
        int count;
    }

그리고 put ( "Word", 새로운 My ( "Word"))을 사용하십시오. 그런 다음 존재하는지 확인하고 추가 할 때 증가시킬 수 있습니다.

내부 루프 검색 및 정렬을 수행하면 성능이 악화되기 때문에 목록을 사용하여 솔루션을 롤링하지 마십시오. 첫 번째 HashMap 솔루션은 실제로 빠르지 만 Google Collections에있는 것과 같은 적절한 것이 더 좋습니다.

Google Collections를 사용하여 단어를 세는 방법은 다음과 같습니다.

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

HashMultiset을 사용하는 것은 매우 정교합니다. 왜냐하면 bag-algorithm은 단어를 집계 할 때 필요한 것이기 때문입니다.

Google Collections HashMultiset :
- 사용하기에 아주 우아합니다.
- 그러나 CPU와 메모리를 소비하십시오.

가장 좋은 방법은 다음과 같습니다. Entry<K,V> getOrPut(K); (우아하고 저렴한 비용)

이러한 메소드는 해시와 인덱스를 한 번만 계산 한 다음 엔트리로 원하는 것을 수행 할 수 있습니다 (값을 바꾸거나 값을 업데이트).

보다 우아함 :
- HashSet<Entry> 가져 가라.
- get(K)이 필요한 경우 새로운 항목을 넣도록 확장하십시오.
- 출품작은 나만의 물건이 될 수 있습니다.
-> (new MyHashSet()).get(k).increment();

약간의 해킹이있는 경우 단일 요소 int 배열을 사용하는 것이 더 빠른 MutableInt 접근법의 변형입니다.

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

이 유사 콘텐츠로 실적 테스트를 재실행 할 수 있다면 흥미로울 것입니다. 그것은 가장 빠를 수도 있습니다.

편집 : 위의 패턴은 저에게 잘 돌아갔습니다.하지만 결국 Trove의 콜렉션을 사용하여 내가 만든 아주 큰지도에서 메모리 크기를 줄 이도록 변경했습니다. 또한 보너스로 더 빨랐습니다.

정말 멋진 기능 중 하나는 TObjectIntHashMap 클래스가 이미 해당 키에 값이 있는지 여부에 따라 초기 값을 지정하거나 기존 값을 증가시키는 단일 adjustOrPutValue 호출을 갖는 것입니다. 이는 증가하는 데 적합합니다.

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

나는 당신의 해결책이 표준적인 방법 일 것이라고 생각하지만, 당신이 스스로 언급했듯이 가능한 가장 빠른 방법이 아닐 것입니다.

당신은 GNU Trove 를 볼 수 있습니다. 그것은 모든 종류의 빠른 기본 컬렉션을 포함하는 라이브러리입니다. 귀하의 예제는 TObjectIntHashMap 당신이 원하는 것을 정확하게 수행하는 adjustOrPutValue 메소드를 사용할 것입니다.

이것이 병목 현상이라고 확신합니까? 성능 분석을 해본 적이 있습니까?

핫스팟을 보려면 NetBeans 프로파일 러 (무료이며 NB 6.1에 내장되어 있음)를 사용해보십시오.

마지막으로, JVM 업그레이드 (1.5 -> 1.6)는 종종 저렴한 성능 향상입니다. 빌드 번호를 업그레이드해도 성능이 향상 될 수 있습니다. Windows에서 실행 중이며 이것이 서버 클래스 어플리케이션 인 경우, 명령 행에서 -server를 사용하여 Server Hotspot JVM을 사용하십시오. Linux 및 Solaris 컴퓨터에서는이 항목이 자동으로 검색됩니다.

아주 간단합니다. Map.Java에 내장 함수를 사용하면됩니다.

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

"put"은 "get"(중복 키가 없음)을 필요로합니다.
그래서 직접 "하다",
이전 값이있는 경우 다음을 추가하십시오.

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
}

Count가 0에서 시작하면 1 : (또는 다른 값 ...)을 추가합니다.

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
}

Notice :이 코드는 스레드로부터 안전하지 않습니다. 이를 사용하여지도를 작성하고 동시에 업데이트하지 마십시오.

Optimization : 루프에서 이전 값을 유지하여 다음 루프의 새 값이됩니다.

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

Eclipse Collections 를 사용하는 경우 HashBag을 사용할 수 있습니다. 메모리 사용 측면에서 가장 효율적인 접근 방법이며 실행 속도 측면에서 잘 수행됩니다.

HashBag은 MutableObjectIntMap 객체 대신 원시 ints를 저장하는 Counter에 의해 뒷받침됩니다. 이는 메모리 오버 헤드를 줄이고 실행 속도를 향상시킵니다.

HashBag은 Collection이므로 필요한 API를 제공하며 항목의 발생 횟수를 쿼리 할 수도 있습니다.

다음은 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"));

주의 : 저는 Eclipse Collections를위한 커미터입니다.

Apache Collections Lazy Map (값을 0으로 초기화)을 사용하고 Apache Lang의 MutableInteger를 해당 맵의 값으로 사용합니다.

가장 큰 비용은 귀하의 방법으로지도를 두 번 세어 볼 필요가 있습니다. 내 경우에는 한 번만해야합니다. 그냥 값을 얻으면 (만약 없다면 초기화 될 것입니다) 그리고 그것을 증가시킵니다.

Functional Java 라이브러리의 TreeMap 데이터 구조에는 최신 트렁크 헤드에 update 메소드가 있습니다.

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

사용 예 :

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

이 프로그램은 "2"를 인쇄합니다.

얼마나 효율적인지는 모르겠지만 아래 코드도 잘 작동합니다. 처음에는 BiFunction을 정의해야합니다. 또한이 방법으로 단순한 것 이상을 만들 수 있습니다.

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

출력은

3
1

다양한 기본 래퍼 (예 : Integer)는 불변이므로 요청한 작업을 수행하는 데 더 간결한 방법이 없습니다. 제외하고 AtomicLong . 나는 잠시 후에 그걸 줄 수 있고 업데이트 할 수있다. BTW, Hashtable is Collections Framework 의 일부.

@Vilmantas Baranauskas :이 대답에 관해서는, 내가 rep 지점이 있다면 나는 논평 하겠지만 나는 그렇지 않다. 거기에 정의 된 Counter 클래스는 value ()를 동기화하지 않고 inc ()를 동기화하는 것만으로는 충분하지 않기 때문에 스레드로부터 안전하지 않습니다. changes ()를 호출하는 다른 스레드는 업데이트와 happen-before 관계가 설정되어 있지 않으면 값을 볼 수 없습니다.