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

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

이 질문이 이 포럼에서 너무 기본적인 질문이 아니었으면 합니다만, 두고 봅시다.여러 번 실행되고 있는 성능을 향상시키기 위해 코드를 어떻게 수정해야 할지 고민하고 있습니다.

예를 들어 맵(HashMap)을 사용하여 워드 빈도 목록을 만듭니다.각 키는 카운트되는 워드의 문자열이고 값은 워드의 토큰이 발견될 때마다 증가하는 정수입니다.

Perl에서는 이러한 값을 늘리는 것은 매우 간단합니다.

$map{$word}++;

하지만 자바에서는 훨씬 더 복잡합니다.현재 제가 하고 있는 방법은 다음과 같습니다.

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

물론 새로운 Java 버전의 자동 박스 기능에 의존합니다.그러한 가치를 높일 수 있는 보다 효율적인 방법을 제안해 주실 수 있는지 궁금합니다.Collections 프레임워크를 사용하지 않고 대신 다른 것을 사용하는 좋은 퍼포먼스 이유가 있습니까?

업데이트: 몇 가지 답을 테스트했습니다.이하를 참조해 주세요.

테스트 결과

저는 이 질문에 대해 좋은 답을 많이 얻었습니다.여러분 감사합니다.그래서 몇 가지 테스트를 해서 어떤 방법이 가장 빠른지 알아보기로 했습니다.테스트한 5가지 방법은 다음과 같습니다.

• 질문에서 제시한 "ContainsKey" 메서드
• 알렉산다르 디미트로프가 제안한 'Test For Null' 방법
• 행크 게이가 제안한 '아토믹 롱' 방법
• Jrudolph가 제안한 'Trove' 방법
• phax.myopenid.com에서 제안하는 'MutableInt' 메서드

방법

내가 한 일은...

1. 는 다음 차이점을 제외하고 동일한 클래스를 5개 만들었습니다.각 클래스는 10MB 파일을 열고 읽은 다음 파일 내의 모든 워드 토큰의 주파수 카운트를 실행하는 전형적인 시나리오의 작업을 수행해야 했습니다.평균 3초밖에 걸리지 않았기 때문에 주파수 카운트(I/O가 아님)를 10회 실행했습니다.
2. 는 I/O 조작이 아닌 10회 반복의 루프를 측정하여 기본적으로 Java Cookbook에 Ian Darwin의 방법을 사용하여 소요된 총 시간(클럭 초)을 기록했습니다.
3. 5개의 테스트를 모두 연속적으로 수행했고, 또 다른 테스트를 3번 수행했습니다.
4. 각 방법에 대한 4가지 결과의 평균을 구했습니다.

결과.

먼저 결과를 제시하고 관심 있는 분들을 위해 아래의 코드를 제시하겠습니다.

Contains Key 메서드가 역시 가장 느렸기 때문에 각 메서드의 속도를 그 메서드의 속도와 비교하여 알려드리겠습니다.

• ContainsKey: 30.654초(기준)
• Atomic Long : 29.780초 (1.03배 고속)
• Test For Null : 28.804초 (1.06배 고속)
• 트로브: 26.313초 (1.16배 빠른 속도)
• MutableInt: 25.747초 (1.19배 고속)

결론들

가능한 것은 인 것 .Int 메서드와 Trove 메서드는 10% 이상의 성능 향상을 제공한다는 점에서 훨씬 더 빠릅니다.그러나 스레드화가 문제가 된다면 Atomic Long이 다른 것보다 더 매력적일 수 있습니다(잘 모르겠습니다). For Null과 Test For 했습니다.final그 차이는 무시할 수 있을 정도였습니다.

다른 시나리오에서는 메모리 사용 현황을 프로파일하지 않았습니다.변이체가 어떻게 변형을 당했는지에 대한 통찰력이 있는 사람이라면 기꺼이 듣고 싶습니다.Int 및 Trove 메서드는 메모리 사용량에 영향을 줄 수 있습니다.

개인적으로, 나는 돌연변이를 발견했어서드파티 클래스를 로드할 필요가 없기 때문에 가장 매력적인 메서드입니다.그래서 문제가 발견되지 않는 한, 그것이 내가 갈 가장 가능성이 높은 방법입니다.

코드

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

Contains Key(키 포함)

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

Test For Null(특수

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

아토믹롱

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

변경가능Int

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에서는 를 사용하여 보다 짧은 방법을 사용할 수 있습니다.

myMap.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

결과: "\"

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

이렇게 단순한 코드로 값을 높일 수 있습니다.

장점:

• 새 클래스를 추가하거나 다른 개념의 가변 int를 사용할 필요가 없습니다.
• 어떤 라이브러리에도 의존하지 않음
• 정확히 무슨 일이 일어나고 있는지 이해하기 쉽다(너무 추상적이지 않음)

단점:

• 해시 맵에서 get()과 put()이 2회 검색됩니다.따라서 가장 성능 좋은 코드는 아닙니다.

이론적으로 get()을 호출하면 배치 위치를 이미 알고 있으므로 다시 검색할 필요가 없습니다.그러나 해시 맵에서 검색하는 데 걸리는 시간은 일반적으로 매우 짧기 때문에 이 성능 문제를 무시할 수 있습니다.

그러나 당신이 이 문제에 대해 매우 진지하다면, 당신은 완벽주의자이며, 다른 방법은 병합 방법을 사용하는 것입니다. 이것은 (이론적으로) 당신이 지도를 한 번만 검색할 수 있기 때문에 (아마도) 이전 코드 조각보다 더 효율적입니다. (이 코드는 첫눈에 분명하지 않지만, 짧고 성능이 우수합니다.)

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

권장사항: 대부분의 경우 코드 가독성에 대해 약간의 성능 향상보다 더 신경을 써야 합니다.첫 번째 코드 스니펫이 이해하기 쉬울 경우 사용합니다.하지만 만약 당신이 두 번째 것을 이해할 수 있다면, 당신은 그것을 할 수 있습니다!

제 코멘트에 대한 후속 조치로서:트로브는 갈 길인 것 같다.어떤 이유로든 표준 JDK를 고수하고 싶다면 ConcurrentMap과 AtomicLong은 YMMV를 사용하더라도 코드를 조금 더 좋게 만들 수 있습니다.

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

1으로서 「」을 참조해 주세요.foo현실적으로 스레드에 대한 친화력 향상만이 이 접근법이 권장하는 전부입니다.

Google Guava는 당신의 친구입니다...

적어도 어떤 경우에는요아토믹 롱맵도 있어요지도에서 가치만큼 오랫동안 다루고 있기 때문에 특히 좋습니다.

예.

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

또한 값에 1보다 많은 값을 추가할 수도 있습니다.

map.getAndAdd(word, 112L); 

Google 컬렉션 라이브러리에서 이러한 내용을 확인하는 것은 항상 좋은 생각입니다.이 경우 멀티셋은 다음과 같은 기능을 수행합니다.

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

키/엔트리 등을 반복하기 위한 Map과 같은 방법이 있습니다.에서는, , 「」를 사용하고 .HashMap<E, AtomicInteger>복싱 비용이 들지 않습니다.

당신은 당신이 처음 시도한 것이

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

맵상의 의 고비용 , 즉 「 연산」을 .containsKey ★★★★★★★★★★★★★★★★★」get전자는 후자와 비슷한 동작을 할 수 있기 때문에 같은 작업을 두 번 하고 있는 것입니다.

Map을 for Map을 보면get, 동작은 반환됩니다.null맵에 요청된 요소가 포함되어 있지 않은 경우.

이를 통해 다음과 같은 솔루션이 생성됩니다.

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

한 일이 도 모르기 NullPointerException s. ㅇㅇㄹ 수 를 확인해 보세요.null 번째. first first first first

그리고 이것은 매우 중요합니다.HashMap는 포함할 수 있습니다.nulls 사람이 돌아온 은 아니다.null「그런 요소는 없습니다」라고 표시됩니다.점에서는, 「 」는, 「 」의containsKey와는 다르게 행동하다get그런 요소가 있는지 아닌지를 알려드립니다.자세한 내용은 API를 참조하십시오.

사용자의 된 " ", " "를 수 .null " Such Element "No Such Element", "No Such Element", "No Such Element"입니다. 」를 null는 s를 할 수 .Hashtable어플리케이션의 복잡성에 따라서는 이미 다른 답변에서 제안한 래퍼 라이브러리를 사용하는 것이 수동 처리의 더 나은 해결책이 될 수 있습니다.

을 완성하는편집 은 원어민으로 하는 입니다.getfinal " ", "를 합니다.null ★★★★★★★★★★★★★★★★★」put와 함께 되돌아가다1는 ''로 해야 합니다.final로 하지 수 그 더 합니다.컴파일러는 이 힌트를 필요로 하지 않을 수 있지만 그 방법이 더 명확합니다.

최종 HashMap 맵= generateRandomHashMap();최종 개체 키 = fetchSomeKey();최종 정수 i = map.get(키);
(i!= null)인 경우,map.put(i + 1);} 기타 {// 뭔가를 하다}

'오토박싱' 같은 .map.put(new Integer(1 + i.getValue()));대신.대신.

다른 방법으로는 가변 정수를 작성하는 방법이 있습니다.

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를 생성하는 것에 비해 오버헤드는 크지 않습니다.

computeIfAbsent 메서드를 사용할 수 있습니다.MapJava 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지정된 키가 값과 이미 관련되어 있는지 여부를 확인합니다.연관된 값이 없는 경우 지정된 매핑 함수를 사용하여 값을 계산하려고 합니다.어떤 경우에도 지정된 키와 관련된 현재(기존 또는 계산된) 값을 반환합니다.무효로 하다

참고로 여러 스레드가 공통 합계를 업데이트하는 경우 LongAdder 클래스를 볼 수 있습니다.경합이 심한 경우 이 클래스의 예상 스루풋은AtomicLong더 많은 공간을 소비하면서 말이죠.

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

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

128보다 크거나 같은 int의 모든 박스가 오브젝트 할당을 일으키기 때문에 메모리 순환이 문제가 될 수 있습니다(integer.valueOf(int) 참조).가비지 콜렉터는 단수명 오브젝트를 매우 효율적으로 처리하지만 퍼포먼스는 어느 정도 저하됩니다.

증가 수가 키 수(이 경우 = 단어)보다 훨씬 많다는 것을 알고 있다면 대신 int 홀더를 사용하는 것을 고려해 보십시오.팩스가 이미 코드를 제시했어요다음 두 가지 변경 사항이 있습니다(홀더 클래스는 정적 및 초기 값을 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을 호출하여 반환된 값이 늘인지 확인하는 것이 빠릅니다.

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

Java 8 Map::compute()를 사용하는 것이 좋습니다.열쇠가 존재하지 않는 경우도 고려합니다.

Map.compute(num, (k, v) -> (v == null) ? 1 : v + 1);

이게 병목 현상인 게 확실해요?퍼포먼스 분석을 해본 적이 있습니까?

NetBeans 프로파일러(무료, NB 6.1에 내장)를 사용하여 핫스팟을 확인합니다.

마지막으로 JVM 업그레이드(1.5→1.6 등)는 저비용 퍼포먼스 부스트인 경우가 많습니다.빌드 번호를 업그레이드해도 성능이 향상됩니다.Windows에서 실행 중이며 서버 클래스 응용 프로그램인 경우 명령줄에서 -server를 사용하여 Server Hotspot JVM을 사용합니다.Linux 및 Solaris 시스템에서는 이 기능이 자동 검출됩니다.

몇 가지 방법이 있습니다.

1. Google 컬렉션에 포함된 세트처럼 가방 알고리즘을 사용합니다.

2. 맵에서 사용할 수 있는 가변 컨테이너를 만듭니다.

    class My{
        String word;
        int count;
    }

그리고 put("word")와 new My("word")를 사용합니다.그 후, 그것이 존재하는지 확인하고 추가할 때 증분할 수 있습니다.

내부 루프 검색 및 정렬이 이루어지면 성능이 저하되므로 목록을 사용하여 자체 솔루션을 롤링하지 마십시오.최초의 HashMap 솔루션은 실제로 매우 빠르지만 Google Collections에 있는 적절한 솔루션이 더 나을 수 있습니다.

Google 컬렉션을 사용하여 단어를 세면 다음과 같습니다.

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

백알고리즘은 단어를 셀 때 꼭 필요한 것이기 때문에 HashMultiset을 사용하는 것은 매우 우아합니다.

변이형 변종좀 더 빠른 방법은 단일 요소 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);

Collections Hash 글글 google google google google 。
- 사용하기에 매우 우아함
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
  }
}

양양양양 、 the the the the the the ） 。Integer 불변하기 때문에 ATOMIC Long과 같은 것을 사용할 수 없는 한 더 간결한 방법은 없습니다.1분 안에 시도해서 업데이트 할 수 있어요.해시 테이블은 컬렉션 프레임워크의 일부입니다.

Apache Collections Lazy Map(값을 0으로 초기화하기 위해)을 사용하고 Mutable을 사용합니다.Apache Lang의 정수를 맵의 값으로 지정합니다.

가장 큰 비용은 당신의 방법으로 지도를 두 번 검색해야 하는 것입니다.내 경우에는 한 번만 하면 돼.값(없을 경우 초기화됨)을 가져와 증가시킵니다.

기능하는 Java 라이브러리의TreeMap에는 「」가 .update"CHANGE: "CHANGE: "CHANGE: " 。

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

이클립스 컬렉션을 사용하는 경우HashBag메모리 사용률 면에서는 가장 효율적인 접근법이 될 것이며 실행 속도 면에서도 뛰어난 성능을 발휘하게 될 것입니다.

HashBag에 의해 백업됩니다.MutableObjectIntMap가 .Counter 속도를 시킵니다.이를 통해 메모리 오버헤드가 감소하고 실행 속도가 향상됩니다.

HashBag이기 때문에 필요한 Collection을 사용법

여기 이클립스 컬렉션 카타의 예가 있습니다.

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의 커밋입니다.

과 ""를 한 "getOrDefault:

String s = "abcdeff";
s.chars().mapToObj(c -> (char) c)
 .forEach(c -> {
     int count = countMap.getOrDefault(c, 0) + 1;
     countMap.put(c, count);
  });

많은 사람들이 Groovy의 답변을 얻기 위해 Java 토픽을 검색하기 때문에 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)

이게 도움이 됐으면 좋겠네요!

Java 8의 심플하고 쉬운 방법은 다음과 같습니다.

final ConcurrentMap<String, AtomicLong> map = new ConcurrentHashMap<String, AtomicLong>();
    map.computeIfAbsent("foo", key -> new AtomicLong(0)).incrementAndGet();

언급URL : https://stackoverflow.com/questions/81346/most-efficient-way-to-increment-a-map-value-in-java