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

https://stackoverflow.com/questions/81346

09-06-2019
|

문제

이 질문이 이 포럼에서 너무 기본적인 것으로 간주되지 않기를 바랍니다. 하지만 살펴보겠습니다.여러 번 실행되는 더 나은 성능을 위해 일부 코드를 리팩터링하는 방법이 궁금합니다.

Map(아마도 HashMap)을 사용하여 단어 빈도 목록을 생성한다고 가정해 보겠습니다. 여기서 각 키는 계산되는 단어가 포함된 문자열이고 값은 단어의 토큰이 발견될 때마다 증가하는 정수입니다.

Perl에서는 이러한 값을 증가시키는 것이 매우 쉽습니다.

$map{$word}++;

그러나 Java에서는 훨씬 더 복잡합니다.제가 현재 하고 있는 방식은 다음과 같습니다.

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

물론 최신 Java 버전의 자동 박싱 기능에 의존합니다.그러한 값을 증가시키는 보다 효율적인 방법을 제안할 수 있는지 궁금합니다.컬렉션 프레임워크를 피하고 대신 다른 것을 사용하는 것이 성능상 좋은 이유가 있습니까?

업데이트:나는 몇 가지 답변에 대한 테스트를 수행했습니다.아래를 참조하세요.

해결책

일부 테스트 결과

저는 이 질문에 대해 많은 좋은 답변을 얻었습니다. 감사합니다. 그래서 몇 가지 테스트를 실행하고 어떤 방법이 실제로 가장 빠른지 알아내기로 결정했습니다.제가 테스트한 다섯 가지 방법은 다음과 같습니다.

제가 제시한 "ContainsKey" 메소드 질문
Aleksandar Dimitrov가 제안한 "TestForNull" 방법
Hank Gay가 제안한 "AtomicLong" 방법
jrudolph가 제안한 "Trove" 방법
phax.myopenid.com에서 제안한 "MutableInt" 방법

방법

내가 한 일은 다음과 같습니다 ...

아래에 표시된 차이점을 제외하고는 동일한 5개의 클래스를 만들었습니다.각 클래스는 내가 제시한 시나리오에 일반적인 작업을 수행해야 했습니다.10MB 파일을 열고 읽은 다음 파일에 있는 모든 단어 토큰의 빈도 계산을 수행합니다.평균 3초 정도 걸리기 때문에 주파수 카운트(I/O 아님)를 10번 수행하게 했습니다.
10회 반복의 루프 시간을 측정했지만 I/O 작업이 아닙니다. 기본적으로 다음을 사용하여 소요된 총 시간(시계 초 단위)을 기록했습니다. Java Cookbook에 있는 Ian Darwin의 방법.
다섯 가지 테스트를 모두 연속적으로 수행한 다음 이 작업을 세 번 더 수행했습니다.
각 방법에 대해 네 가지 결과를 평균화했습니다.

결과

관심있는 분들을 위해 먼저 결과를 보여드리고 아래 코드를 보여드리겠습니다.

그만큼 키 포함 방법은 예상대로 가장 느렸습니다. 따라서 각 방법의 속도를 해당 방법의 속도와 비교하여 설명하겠습니다.

포함키: 30.654초(기준)
원자 길이: 29.780초 (1.03배 빠른 속도)
테스트ForNull: 28.804초 (1.06배 빠른 속도)
트로브: 26.313초 (1.16배 빠른 속도)
가변인트: 25.747초 (1.19배 빠른 속도)

결론

MutableInt 메서드와 Trove 메서드만 10% 이상의 성능 향상을 제공한다는 점에서 훨씬 더 빠른 것으로 보입니다.그러나 스레딩이 문제라면 AtomicLong이 다른 것보다 더 매력적일 수 있습니다(확실하지는 않습니다).나는 또한 TestForNull을 다음과 같이 실행했습니다. final 변수가 있었지만 그 차이는 미미했습니다.

다양한 시나리오에서 메모리 사용량을 프로파일링하지 않았습니다.MutableInt 및 Trove 메서드가 메모리 사용량에 어떤 영향을 미칠지에 대한 좋은 통찰력을 갖고 있는 사람의 의견을 듣고 싶습니다.

개인적으로 저는 MutableInt 메서드가 타사 클래스를 로드할 필요가 없기 때문에 가장 매력적이라고 생각합니다.따라서 문제가 발견되지 않는 한 나는 그 길을 갈 가능성이 가장 높습니다.

코드

다음은 각 메서드의 중요한 코드입니다.

키 포함

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

트로피

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

다른 팁

좋습니다. 오래된 질문일 수 있지만 Java 8에는 더 짧은 방법이 있습니다.

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

그것이 하는 일:만약에 열쇠 존재하지 않는다, 넣어라 1 값으로, 그렇지 않으면 합계 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 구아바 당신의 친구입니다...

...적어도 어떤 경우에는요.그들은 이것을 좋아한다 원자긴지도.당신이 다루고 있기 때문에 특히 좋습니다 긴 지도의 값으로.

예:

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

값에 1 이상을 추가할 수도 있습니다.

map.getAndAdd(word, 112L);

@행크 게이

내 자신의 (다소 쓸모없는) 의견에 대한 후속 조치로:트로브가 갈 길인 것 같습니다.어떤 이유로든 표준 JDK를 고수하고 싶다면, 동시 맵 그리고 AtomicLong 코드를 만들 수 있습니다 매우 작은 조금 더 좋지만 YMMV.

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

떠날 것이다 1 지도의 값으로 foo.현실적으로 이 접근 방식이 권장하는 것은 스레딩에 대한 친화성 향상뿐입니다.

항상 잘 살펴보는 것이 좋습니다. Google 컬렉션 라이브러리 이런 일을 위해서.이 경우에는 다중 집합 트릭을 할 것입니다 :

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

키/항목 등을 반복하는 맵과 유사한 메서드가 있습니다.내부적으로 구현은 현재 HashMap<E, AtomicInteger>, 복싱 비용이 발생하지 않습니다.

당신은 당신의 원래 시도가

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

지도에는 잠재적으로 비용이 많이 드는 두 가지 작업이 포함되어 있습니다. containsKey 그리고 get.전자는 잠재적으로 후자와 매우 유사한 작업을 수행하므로 동일한 작업을 수행하게 됩니다. 두 배!

지도용 API를 보면, get 작업은 일반적으로 반환 null 지도에 요청한 요소가 포함되어 있지 않은 경우.

이것은 다음과 같은 솔루션을 만들 것입니다.

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

위험하다, 양보할 수도 있기 때문에 NullPointerException에스.당신은 null 첫 번째.

또한 참고, 그리고 이것은 매우 중요합니다. HashMap에스 ~할 수 있다 포함하다 nulls 정의상.그래서 모두가 돌아오지는 않았어 null "그런 요소가 없다"고 하네요.이와 관련하여, containsKey 행동하다 다르게 ~에서 get 사실 너한테 말하면서 ~이든 그런 요소가 있어요.자세한 내용은 API를 참조하세요.

그러나 귀하의 경우 저장된 항목을 구별하고 싶지 않을 수도 있습니다. null 그리고 "noSuchElement".허락하고 싶지 않다면 null그럼 당신은 아마 Hashtable.다른 답변에서 이미 제안된 래퍼 라이브러리를 사용하는 것이 애플리케이션의 복잡성에 따라 수동 처리에 대한 더 나은 솔루션일 수 있습니다.

답변을 완성하려면(편집 기능 덕분에 처음에 입력하는 것을 잊어버렸습니다!) 기본적으로 가장 좋은 방법은 다음과 같습니다. get 으로 final 변수, 확인 null 그리고 put 그것은 다시 1.변수는 final 어쨌든 불변이기 때문입니다.컴파일러에는 이 힌트가 필요하지 않을 수도 있지만 그렇게 하는 것이 더 명확합니다.

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

오토박싱에 의존하고 싶지 않다면 다음과 같이 말해야 합니다. 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를 생성하는 것(Integer.valueOf를 사용하더라도)에 비해 오버헤드가 그리 크지 않아야 합니다.

당신은 활용할 수 있습니다 계산IfAbsent 방법 Map 제공되는 인터페이스 자바 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]

방법 computeIfAbsent 지정된 키가 이미 값과 연결되어 있는지 확인합니다.연관된 값이 없으면 지정된 매핑 함수를 사용하여 해당 값을 계산하려고 시도합니다.어떤 경우든 지정된 키와 연관된 현재(기존 또는 계산된) 값을 반환하거나, 계산된 값이 null인 경우 null을 반환합니다.

참고로 여러 스레드가 공통 합계를 업데이트하는 상황이 있는 경우 다음을 살펴볼 수 있습니다. 장가산기 클래스.경합이 심한 경우 이 클래스의 예상 처리량은 다음보다 훨씬 높습니다. 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 구현을 찾으십시오.루돌프가 언급됨 GNU 트로피.

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

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

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

이것이 병목 현상이라고 확신합니까?성능 분석을 해보셨나요?

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

마지막으로 JVM 업그레이드(예: 1.5->1.6)는 종종 저렴한 성능 향상 도구입니다.빌드 번호를 업그레이드해도 성능이 향상될 수 있습니다.Windows에서 실행 중이고 서버 클래스 애플리케이션인 경우 명령줄에서 -server를 사용하여 서버 핫스팟 JVM을 사용하세요.Linux 및 Solaris 시스템에서는 자동으로 감지됩니다.

몇 가지 접근 방식이 있습니다.

Google 컬렉션에 포함된 세트와 같은 Bag 알고리즘을 사용하세요.
맵에서 사용할 수 있는 변경 가능한 컨테이너를 만듭니다.


    class My{
        String word;
        int count;
    }

그리고 put("word", new My("Word") );그런 다음 존재하는지 확인하고 추가할 때 증가할 수 있습니다.

내부 루프 검색 및 정렬을 수행하면 성능이 저하되므로 목록을 사용하여 자체 솔루션을 롤링하지 마십시오.첫 번째 HashMap 솔루션은 실제로 매우 빠르지만 Google 컬렉션에 있는 것과 유사한 솔루션이 더 나을 것입니다.

Google 컬렉션을 사용하여 단어 수를 계산하는 방법은 다음과 같습니다.



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

HashMultiset을 사용하는 것은 매우 우아합니다. 왜냐하면 가방 알고리즘은 단어를 계산할 때 꼭 필요한 것이기 때문입니다.

나는 귀하의 솔루션이 표준 방법이라고 생각하지만, 귀하가 직접 언급했듯이 아마도 가장 빠른 방법은 아닐 것입니다.

당신은 볼 수 있습니다 GNU 트로피.이는 모든 종류의 빠른 기본 컬렉션을 포함하는 라이브러리입니다.귀하의 예에서는 TObjectIntHashMap 원하는 것을 정확하게 수행하는 adjustOrPutValue 메소드가 있습니다.

약간의 해킹이라면 훨씬 더 빠를 수 있는 MutableInt 접근 방식의 변형은 단일 요소 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];

이 변형을 사용하여 성능 테스트를 다시 실행할 수 있다면 흥미로울 것입니다.가장 빠른 것일 수도 있습니다.

편집하다:위의 패턴은 제게는 괜찮았지만 결국 제가 만들고 있는 매우 큰 일부 맵에서 메모리 크기를 줄이기 위해 Trove의 컬렉션을 사용하도록 변경했습니다. 그리고 보너스로 속도도 더 빨라졌습니다.

정말 좋은 기능 중 하나는 TObjectIntHashMap 수업은 하나입니다 adjustOrPutValue 해당 키에 이미 값이 있는지 여부에 따라 초기 값을 넣거나 기존 값을 증가시키는 호출입니다.이는 다음을 증가시키는 데 적합합니다.

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

Google 컬렉션 HashMultiset :
- 사용하기 매우 우아함
- 하지만 CPU와 메모리를 소모합니다.

가장 좋은 방법은 다음과 같은 방법을 사용하는 것입니다. Entry<K,V> getOrPut(K); (우아하고 가격이 저렴함)

이러한 방법은 해시와 색인을 한 번만 계산 한 다음 항목으로 원하는 것을 수행 할 수 있습니다 (값을 바꾸거나 업데이트).

더 우아함:
- 가져가 HashSet<Entry>
- 그렇게 연장해라 get(K) 필요한 경우 새 항목을 넣으십시오.
- 항목은 자신의 개체가 될 수 있습니다.
--> (new MyHashSet()).get(k).increment();

"put"에는 "get"이 필요합니다(중복 키가 없도록 하기 위해).
따라서 직접 "put"을 수행하고,
이전 값이 있는 경우 추가를 수행합니다.

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
}

개수가 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
}

알아채다 : 이 코드는 스레드로부터 안전하지 않습니다.이를 사용하여 맵을 빌드한 다음 동시에 업데이트하지 않고 맵을 사용하십시오.

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

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

다양한 기본 래퍼(예: Integer 불변이므로 요청한 작업을 수행하는 이보다 더 간결한 방법은 없습니다. ~하지 않는 한 당신은 같은 것으로 그것을 할 수 있습니다 AtomicLong.잠시 후에 업데이트해 보겠습니다.그런데, 해시테이블 ~이다 ~의 일부 컬렉션 프레임워크.

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

가장 큰 비용은 귀하의 방법에서 지도를 두 번 검색해야 한다는 것입니다.내 경우에는 한 번만 수행하면 됩니다.값을 가져와서(없으면 초기화됨) 값을 증가시키세요.

그만큼 기능적 자바 도서관의 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"를 인쇄합니다.

@Vilmantas Baranauskas:이 답변과 관련하여 담당자 포인트가 있으면 언급하고 싶지만 그렇지 않습니다.value()를 동기화하지 않고 inc()를 동기화하는 것만으로는 충분하지 않기 때문에 거기에 정의된 Counter 클래스는 스레드로부터 안전하지 않다는 점에 주목하고 싶었습니다.value()를 호출하는 다른 스레드는 업데이트와 함께 사전 발생 관계가 설정되지 않는 한 값을 확인하는 것이 보장되지 않습니다.

얼마나 효율적인지는 모르겠지만 아래 코드도 잘 작동합니다. 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

당신이 사용하는 경우 이클립스 컬렉션, 당신은 HashBag.이는 메모리 사용량 측면에서 가장 효율적인 접근 방식이 될 것이며 실행 속도 측면에서도 좋은 성능을 발휘할 것입니다.

HashBag 의 지원을 받습니다 MutableObjectIntMap 대신 기본 int를 저장합니다. Counter 사물.이렇게 하면 메모리 오버헤드가 줄어들고 실행 속도가 향상됩니다.

HashBag 필요한 API를 제공합니다. Collection 또한 항목의 발생 횟수를 쿼리할 수도 있습니다.

다음은 Eclipse 컬렉션 카타.

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 컬렉션의 커미터입니다.

매우 간단합니다. 내장된 기능을 사용하면 됩니다. Map.java 다음과 같이

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

많은 사람들이 Java 주제에서 Groovy 답변을 검색하므로 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}

귀하의 질문을 올바르게 이해하고 있기를 바랍니다. 저는 귀하의 어려움에 공감할 수 있도록 Python에서 Java로 왔습니다.

당신이 가지고 있다면

map.put(key, 1)

당신은 할 것이다

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

도움이 되었기를 바랍니다!

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow