[解決済み】JavaでMap値をインクリメントする最も効率的な方法

2022-01-26 11:40:53

質問

この質問がこのフォーラムにとってあまりに基本的すぎると見なされないことを望みますが、見てみましょう。私は、何度も実行されているパフォーマンスを向上させるために、いくつかのコードをリファクタリングする方法について考えています。

Map（おそらくHashMap）を使って、単語の頻度リストを作成するとします。各キーはカウントされる単語を表す文字列で、値はその単語のトークンが見つかるたびに増分される整数です。

Perlでは、このような値の増加は些細なことである。

$map{$word}++;

しかし、Javaでは、もっと複雑です。ここでは、私が現在行っている方法を紹介します。

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

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

更新：いくつかの回答についてテストしてみました。以下を参照してください。

解決方法は？

テスト結果

この質問に対して多くの良い回答をいただきました。皆さんありがとうございます。テストしたのは、以下の5つの方法だ。

で紹介した "ContainsKey" メソッド。質問
Aleksandar Dimitrovが提案したquot;TestForNull"メソッド。
Hank Gay氏によって提案されたquot;AtomicLong"メソッド。
jrudolphが提案したquot;Trove"メソッド。
phax.myopenid.com が提案する MutableInt" メソッド。

メソッド

ここで、私がやったことは......。

は、以下に示す違いを除き、同じクラスを5つ作成した。各クラスは、10MBのファイルを開いて読み込み、ファイル内のすべての単語トークンの頻度カウントを実行するという、私が提示したシナリオに典型的な操作を行う必要がありました。これは平均3秒しかかからないので、I/Oではなく頻度カウントを10回実行させた。
10回繰り返しのループをタイムアウトさせたが I/O操作ではなく を使用して、かかった合計時間（クロック秒）を記録しました。 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();
}