java - Java で Map 値をインクリメントする最も効率的な方法

Question

この質問がこのフォーラムにとって基本的すぎると見なされないことを願っていますが、見ていきます。何度も実行されるパフォーマンスを向上させるために、一部のコードをリファクタリングする方法を考えています。

Map (おそらく HashMap) を使用して単語頻度リストを作成しているとします。ここで、各キーはカウントされる単語を含む文字列であり、値は単語のトークンが見つかるたびにインクリメントされる整数です。

Perl では、このような値をインクリメントするのは簡単です:

$map{$word}++;

しかし、Java では、それははるかに複雑です。ここで私が現在やっている方法：

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

もちろん、これは新しい Java バージョンのオートボクシング機能に依存しています。そのような値をインクリメントするより効率的な方法を提案していただけないでしょうか。Collections フレームワークを避けて、代わりに何か他のものを使用するための良いパフォーマンス上の理由はありますか?

更新:いくつかの回答のテストを行いました。下記参照。

score 415 · Accepted Answer

いくつかのテスト結果

私はこの質問に対して多くの良い答えを得ました - 皆さんに感謝します - そこで私はいくつかのテストを実行し、どの方法が実際に最速であるかを理解することにしました. 私がテストした5つの方法は次のとおりです。

質問で提示した「ContainsKey」メソッド
Aleksandar Dimitrov によって提案された "TestForNull" メソッド
ハンク・ゲイが提案した「AtomicLong」メソッド
jrudolph によって提案された "Trove" メソッド
phax.myopenid.com によって提案された「MutableInt」メソッド

方法

これが私がやったことです...

以下に示す違いを除いて同一の 5 つのクラスを作成しました。各クラスは、私が提示したシナリオに典型的な操作を実行する必要がありました。10 MB のファイルを開いて読み込み、ファイル内のすべての単語トークンの頻度カウントを実行しました。平均で 3 秒しかかからなかったので、(I/O ではなく) 頻度カウントを 10 回実行しました。
I/O 操作ではなく10 回の反復のループの時間を計り、Java Cookbook の Ian Darwin の方法を基本的に使用して、合計所要時間 (クロック秒単位) を記録しました。
一連の 5 つのテストすべてを実行し、これをさらに 3 回実行しました。
各メソッドの 4 つの結果を平均します。

結果

最初に結果を示し、興味のある方のために以下のコードを示します。

予想どおり、 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 が他のものよりも魅力的かもしれません (よくわかりません)。変数を指定して 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);
}

アトミックロング

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

score 48 · Accepted Answer

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

時間\空間の結果:

score 40 · Accepted Answer

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() を呼び出した時点で put() の場所がわかっているため、再度検索する必要はありません。ただし、通常、ハッシュマップでの検索にかかる時間はごくわずかなので、このパフォーマンスの問題は無視できます。

しかし、あなたが問題について非常に真剣に考えている場合、あなたは完璧主義者です。別の方法は、マージメソッドを使用することです。これは、(理論的には) マップを 1 回だけ検索するため、前のコードスニペットよりも (おそらく) 効率的です。このコードは一見しただけではわかりません。短くて高性能です)

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

提案: ほとんどの場合、コードの可読性を気にする必要があります。最初のコードスニペットの方が理解しやすい場合は、それを使用してください。でも、2つ目もちゃんと理解できれば大丈夫！

score 38 · Accepted Answer

私自身のコメントへのフォローアップとして：Troveは行くべき道のように見えます. なんらかの理由で、標準の 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。現実的には、このアプローチが推奨する必要があるのは、スレッドへの親しみやすさの向上だけです。

score 37 · Accepted Answer

Google Guavaはあなたの友達です...

...少なくとも場合によっては。彼らはこの素敵なAtomicLongMapを持っています。マップ内の値として長く扱っているため、特に便利です。

例えば

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

値に 1 以上を追加することもできます。

map.getAndAdd(word, 112L);

score 28 · Accepted Answer

この種のものについては、 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 のようなメソッドがあります。内部的に、実装は現在を使用しているHashMap<E, AtomicInteger>ため、ボックス化のコストは発生しません。

score 23 · Accepted Answer

あなたの最初の試みが

int カウント = map.containsKey(word) ? map.get(単語): 0;

には、マップ上でコストがかかる可能性のある 2 つの操作、つまりcontainsKeyとが含まれていますget。前者は後者と非常によく似た操作を実行する可能性があるため、同じ作業を 2 回行うことになります。

Map の API を見ると、get通常、操作はnull要求された要素がマップに含まれていない場合に返されます。

これにより、次のようなソリューションが作成されることに注意してください

map.put(キー、map.get(キー) + 1);

危険NullPointerExceptionです。null最初に確認する必要があります。

また、これは非常に重要なことですが、定義によりHashMapsを含むことができることに注意してください。nullsしたがって、返されるすべてnullのものが「そのような要素はありません」と言うわけではありません。この点で、実際にそのような要素があるかどうかを伝える場合とは異なるcontainsKey動作をします。詳細については、API を参照してください。 get

ただし、あなたの場合、保存されたものnullと「noSuchElement」を区別したくない場合があります。nullsを許可したくない場合は、 Hashtable. アプリケーションの複雑さによっては、他の回答で既に提案されているようにラッパーライブラリを使用する方が、手動処理のより良い解決策になる場合があります。

答えを完成させるには (そして、編集機能のおかげで、最初にそれを入れるのを忘れていました!)、それをネイティブに行う最善の方法は、変数にget入れ、をチェックして、で戻すことです。とにかく不変であるため、変数はそうあるべきです。コンパイラはこのヒントを必要としないかもしれませんが、その方がより明確です。finalnullput1final

最終的な HashMap マップ = generateRandomHashMap();
最終的なオブジェクト キー = fetchSomeKey();
最終整数 i = map.get(key);
if (i != null) {
    map.put(i + 1);
} そうしないと {
    //何かをする
}

オートボクシングに頼りたくない場合は、map.put(new Integer(1 + i.getValue()));代わりに次のように言う必要があります。

score 20 · Accepted Answer

別の方法は、可変整数を作成することです。

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 を作成する場合と比較してオーバーヘッドはそれほど大きくないはずです。

score 9 · Accepted Answer

非常に簡単です。次のように組み込み関数を使用するだけMap.javaです

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

score 8 · Accepted Answer

128 以上の int をボックス化するたびにオブジェクトが割り当てられるため、ここではメモリローテーションが問題になる可能性があります (Integer.valueOf(int) を参照)。ガベージコレクタは有効期間の短いオブジェクトを非常に効率的に処理しますが、パフォーマンスはある程度低下します。

増分の数がキーの数 (この場合は単語数) を大幅に上回ることがわかっている場合は、代わりに int ホルダーの使用を検討してください。Phax は、このためのコードを既に提示しています。ここでも、2 つの変更があります (ホルダークラスが静的になり、初期値が 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について言及しました。

ちなみに、このテーマの良い検索用語は「ヒストグラム」です。

score 5 · Accepted Answer

containsKey（）を呼び出す代わりに、map.getを呼び出して、戻り値がnullかどうかを確認する方が高速です。

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

score 3 · Accepted Answer

いくつかのアプローチがあります。

Google コレクションに含まれるセットのような Bag アルゴリズムを使用します。
Map で使用できる可変コンテナーを作成します。


    class My{
        String word;
        int count;
    }

put("word", new My("Word") ); を使用します。次に、それが存在するかどうかを確認し、追加するときにインクリメントできます。

リストを使用して独自のソリューションを展開することは避けてください。内部ループの検索と並べ替えを行うと、パフォーマンスが低下するためです。最初の HashMap ソリューションは実際には非常に高速ですが、Google Collections にあるような適切なソリューションの方がおそらく優れています。

Google Collections を使用して単語をカウントすると、次のようになります。



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

HashMultiset の使用は非常にエレガントです。なぜなら、バッグアルゴリズムは単語を数えるときに必要なものだからです。

score 3 · Accepted Answer

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 のコレクションを使用して、作成していた非常に大きなマップのメモリサイズを削減するように変更しました。ボーナスとして、それも高速でした。

非常に優れた機能の 1 つは、そのキーに値が既に存在するかどうかに応じて、初期値を設定するか、既存の値をインクリメントするTObjectIntHashMap単一の呼び出しがクラスにあることです。adjustOrPutValueこれはインクリメントに最適です：

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

score 3 · Accepted Answer

これがボトルネックであると確信していますか? パフォーマンス分析を行ったことはありますか?

ホットスポットを調べるには、NetBeans プロファイラー (無料で NB 6.1 に組み込まれています) を使用してみてください。

最後に、JVM のアップグレード (たとえば 1.5 から 1.6 へ) は、多くの場合、安価なパフォーマンスブースターです。ビルド番号をアップグレードしても、パフォーマンスが大幅に向上します。Windows で実行していて、これがサーバークラスのアプリケーションである場合は、コマンドラインで -server を使用してサーバーホットスポット JVM を使用します。Linux および Solaris マシンでは、これは自動検出されます。

score 3 · Accepted Answer

Google Collections HashMultiset :
- 使い方は非常に洗練されています
が、CPU とメモリを消費します

次のような方法が最適です:(Entry<K,V> getOrPut(K); エレガントで低コスト)

このようなメソッドは、ハッシュとインデックスを 1 回だけ計算し、その後、エントリに対して必要なことを行うことができます (値の置換または更新)。

よりエレガント:
- 取る-必要に応じて新しいエントリHashSet<Entry>
を配置するように拡張する - エントリは独自のオブジェクトにすることができます。 -->get(K)

(new MyHashSet()).get(k).increment();

score 2 · Accepted Answer

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

カウントが 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
  }
}

score 1 · Accepted Answer

Apache Collections Lazy Map (値を 0 に初期化するため) を使用し、Apache Lang の MutableIntegers をそのマップの値として使用します。

最大のコストは、メソッドでマップを 2 回検索する必要があることです。私の場合は、一度だけ行う必要があります。値を取得して (存在しない場合は初期化されます)、インクリメントします。

score 1 · Accepted Answer

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」を出力します。

score 1 · Accepted Answer

たとえば、さまざまなプリミティブラッパーは不変であるため、 AtomicLongのようなもので実行できない限りInteger、求めていることをより簡潔に実行する方法は実際にはありません。すぐに試して更新できます。ところで、HashtableはCollections Frameworkの一部です。

score 1 · Accepted Answer

Eclipse Collectionsを使用している場合は、HashBag. これは、メモリ使用量の点で最も効率的なアプローチであり、実行速度の点でも優れています。

HashBagMutableObjectIntMapオブジェクトの代わりにプリミティブ int を格納するによってサポートされてい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 コレクションのコミッターです。