it-swarm-ko.tech

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

나는이 질문이이 포럼을 위해 너무 기본적인 것으로 생각하지 않기를 바란다. 그러나 우리는 보게 될 것이다. 좀 더 나은 성능을 위해 몇 가지 코드를 리팩터링하는 방법에 대해 궁금합니다.

Map (아마도 HashMap)을 사용하여 단어 빈도 목록을 만들고 있다고 가정 해보십시오. 각 키는 계산되는 Word의 String이며 값은 Word의 토큰이 발견 될 때마다 증가되는 정수입니다.

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

$map{$Word}++;

하지만 Java에서는 훨씬 더 복잡합니다. 여기 내가 현재하고있는 방법 :

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

물론 최신 Java 버전의 autoboxing 기능에 의존합니다. 나는 당신이 그런 가치를 증가시키는보다 효율적인 방법을 제안 할 수 있는지 궁금합니다. Collections 프레임 워크를 피하고 대신 다른 것을 사용하는 것이 좋은 성능상의 이유가 있습니까?

업데이트 : 몇 가지 답변을 테스트했습니다. 아래를 참조하십시오.

327
gregory

일부 검사 결과

이 질문에 대한 많은 좋은 답변을 얻었습니다. - 감사합니다. - 그래서 몇 가지 테스트를 실행하고 실제로 가장 빠른 방법을 찾아 냈습니다. 테스트 한 다섯 가지 방법은 다음과 같습니다.

  • 내가 제시 한 "ContainsKey"메쏘드 질문
  • aleksandar Dimitrov가 제안한 "TestForNull"방법
  • 행크 게이가 제안한 "AtomicLong"방법
  • jrudolph가 제안한 "Trove"방법
  • phax.myopenid.com에서 제안한 "MutableInt"메소드

방법

내가 한 일은 ...

  1. 아래에 표시된 차이점을 제외하고는 동일한 5 개의 클래스를 만들었습니다. 각 클래스는 필자가 제시 한 시나리오에서 일반적인 작업을 수행해야했습니다. 10MB 파일을 열고 파일을 읽은 다음 파일에서 모든 Word 토큰의 빈도를 계산합니다. 이것은 평균 3 초 밖에 걸리지 않았으므로 주파수 카운트 (I/O가 아닌)를 10 번 수행했습니다.
  2. 10 개의 반복 루프를 시간을 재었지만 I/O 연산이 아닌 본질적으로 Java Cookbook의 Ian Darwin의 방법 를 사용하여 취한 총 시간 (초)을 기록했습니다.
  3. 일련의 다섯 가지 테스트를 모두 수행 한 다음 세 번 더 테스트를 수행했습니다.
  4. 각 방법에 대해 4 개의 결과를 평균했다.

결과

관심있는 사람들을 위해 먼저 결과를 제시하고 아래 코드를 제공 할 것입니다.

ContainsKey ContainsKey 메서드는 예상대로 속도가 가장 느 렸기 때문에 각 메서드의 속도를 해당 메서드의 속도와 비교해 보겠습니다.

  • ContainsKey : 30.654 초 (기준선)
  • AtomicLong : 29.780 초 (1.03 배 빠름)
  • TestForNull : 28.804 초 (1.06 배 빠름)
  • Trove : 26.313 초 (1.16 배 빠름)
  • MutableInt : 25.747 초 (1.19 배 빠름)

결론

MutableInt 메소드와 Trove 메소드 만이 10 % 이상의 성능 향상을 제공한다는 점에서 상당히 빠르다. 그러나 스레딩이 문제가되면 AtomicLong이 다른 것보다 매력적일 수 있습니다 (확실하지 않습니다). final 변수를 사용하여 TestForNull도 실행했지만 그 차이는 무시할 수있었습니다.

다른 시나리오에서 메모리 사용량을 프로파일 링하지 않았습니다. MutableInt 및 Trove 메서드가 메모리 사용에 영향을 줄 수있는 방법에 대한 좋은 통찰력을 가진 사람의 의견을 듣고 기쁘게 생각합니다.

개인적으로 MutableInt 메서드는 타사 클래스를로드 할 필요가 없기 때문에 가장 매력적입니다. 그래서 내가 문제를 발견하지 못하면, 그것이 내가 가장 할 수있는 방법입니다.

코드

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

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

참다

import gnu.trove.TObjectIntHashMap;
...
TObjectIntHashMap<String> freq = new TObjectIntHashMap<String>();
...
freq.adjustOrPutValue(Word, 1, 1);

변경 가능 항목

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

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

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

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

175
LE GALL Benoît

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

시간\공간 결과 : 

42
leventov

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

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

예 :.

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

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

map.getAndAdd(Word, 112L); 
33
H6.

@ 행크 게이

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

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

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

31
Hank Gay

이런 종류의 일에 대해 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>를 사용하므로 복싱 비용이 발생하지 않습니다.

25
Chris Nokleberg

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

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

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

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 변수를 넣고 nullput 변수를 확인하고 1 . 변수는 어쨌든 불변이므로 final이어야합니다. 컴파일러는이 힌트를 필요로하지 않을 수도 있지만, 그렇게 명확하다.

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

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

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

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

20
off99555

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

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를 만드는 것과 비교할 때 발생하는 오버 헤드는 그렇게 많이해서는 안됩니다.

18
Philip Helger

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보다 상당히 높습니다. 더 많은 공간을 소비합니다.

9
i_am_zero

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 .

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

7
volley

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

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

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

  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은 단어를 집계 할 때 필요한 것이기 때문입니다.

3
tovare

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

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

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

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

3
the felis leo

약간의 해킹이있는 경우 단일 요소 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);
3

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

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

3
jrudolph

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

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

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

3
John Wright

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

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

"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
  }
}
2
the felis leo

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

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

HashBagCollection이므로 필요한 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를위한 커미터입니다.

1
Craig P. Motlin

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

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

1
jb.

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"를 인쇄합니다.

1
Apocalisp

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

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

1
Hank Gay

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

1
Alex Miller