S-JIS[2009-03-04/2009-03-25] 変更履歴

Javaのコスト

コストと一言で言ってもいろいろな意味があるが、ここでは実行時のコストについて考えてみる。

テスト用ソース： cost.src.zip

基本的な処理にかかる時間

インスタンス生成（new）やthrow-catchといった基本操作にかかる時間を調べてみた。（WindowsXP、Eclipse3.4）[2009-03-05]

インスタンス生成と一口に言っても、クラスによって全然速度が違う。（コンストラクターの内容次第だろうから、当たり前だけど）
でもJDK1.6ではけっこう高速化が図られているようだ。

//throw-catch
	Exception t = new RuntimeException();
	try { throw t; }catch(Exception e){}		←これをループ
//synchronized
	synchronized(クラス.class) { }		←これをループ

try〜catchはJDK1.6で速くなっている。
逆に空ループはJDK1.4→JDK1.5で微妙に遅くなっている。とは言っても100万回で1ミリ秒未満なら、他の実行速度に比べると無視できる話だ。
synchronizedはJDK1.5で速くなったのに、JDK1.6で遅くなっている。何が変わったんだろうなぁ？

synchronizedは確かに無処理に比べれば遅いが、インスタンス生成と比べれば、文字列結合2〜3個分と同じくらい？
もちろんマルチスレッドの競合の頻度にもよるだろうけど、そんなに目くじら立てるほど遅くない気がする。

instanceofは、JDKのバージョンによる速度の違いはあまり無いようだ。[2009-03-07]

それにしても、
「obj instanceof クラス」は、objがそのクラスのインスタンスであっても無くてもほとんど速度の差は無いが、
「obj instanceof インターフェース」は、objがそのインターフェースを実装しているかどうかで10倍くらい速度が違う！
（その遅い場合でも、StringやStringBuilderのインスタンス生成よりは速いけど）

インターフェースを実装している場合はすぐ結論が出るけれど、実装していない場合は調べるものが多いから遅いのだろうか。
・全ての親クラスが該当インターフェースを実装しているかどうか調べないといけない
・実装している全インターフェースが該当インターフェースを継承しているかどうかも調べないといけない

クラス c = (クラス)obj;

if (obj instanceof クラス) {
  クラス c = (クラス)obj;
}

try {
  クラス c = (クラス)obj;
} catch (ClassCastException e) {}

「作っているプログラムの仕様上、オブジェクトが必ずそのクラスにキャストできる」と分かっているなら、ただ単にキャストすればいい。
クラスが違う可能性もあるなら、instanceofもペアにして使う。
この実行速度なら、違う可能性が低い場合はClassCastExceptionをキャッチするコーディングも有り…なのかなぁ？
違う可能性が高いのにClassCastExceptionをキャッチして続行するようなプログラムは、かなり（1000倍以上）効率悪そう。

contains()の速度

値の一覧の中から、ある値が存在しているかどうかを調べるには、Map#containskey()（Set#contains()）を使う。[2009-03-04]
が、ハッシュマップはハッシュ値を計算したりする手間があるので、個数が少ないならList#contains()の方が速いんじゃないかと思ってちょっと速度を測ってみた。（WindowsXP、Eclipse3.4）

なお、値一覧は固定という想定で、コレクション（MapやList）の生成や変更のコストは考慮に含めない。

下記の表の中の各バージョン毎の数値は、左から順に
Arrays#binarySearch()、ArrayList#contains()、HashMap#containsKey()

「コレクション内の個数（要素数）が少ないならHashMap#containsKey()よりArrayList#contains()の方が速い」ということ自体は予想通りだけれども、その「少ないなら」の具体的な数値は「1個まで」か！(爆)
キーがStringの場合、JDK1.4では少なくとも要素数3個でHashMapの方が速くなるが、JDK1.5以降は要素数2個で速くなる。
また、JDK1.4の場合はArrayListに対するStringの桁数の影響も大きく、String6桁だと要素数2個でHashMapの方が速くなる。

結局のところ、equals()での文字列比較は文字数の回数だけ比較を行うので、ハッシュ値の計算を先に行っても比較にそのハッシュ値を使う方が速くなるのだろう。
Integerの場合はequals()は単純なので、要素数2個でもArrayListの方がHashMapより速いのだろう。

なお、リストの先頭でマッチするキーで検索をかける場合は、要素数に関わらずArrayListの方がHashMapより速い。
とは言っても、どんなに要素数が多くなっても HashMapはArrayListより一定時間遅いだけなので、優秀だ。
逆にリストの末尾でマッチするキーで検索をかけると、ArrayListは要素数が多いほど比例して時間がかかる（リストとは当然そういうものだ）のに対し、HashMapはもっと短時間（ほぼ一定時間（厳密にはオーダーの…いくつだったっけ？(爆)））で終わる（それでこそマップだ）。

それにしても、JREのバージョンによってかなり速度が違うのに驚き。JDK1.4のこの遅さは何なんだ(苦笑)
String・Integerを扱うArrayList・HashMapの両方共、JDK1.4よりJDK1.5以降の方がずっと高速。
Stringの場合は、ArrayListもHashMapもJDK1.6でさらにJDK1.5より高速になってる。
逆にIntegerをキーとして扱うのは、HashMapはJDK1.6で少し遅くなっているようだが…ArrayListは若干速い。

結論

変化しない一覧を保持して存在有無をチェックするような場合、HashMap#containsKey()（HashSet#contains()）を使うのがいい。
（そういう使い方をする場合、要素数が2個なんてことはまず有り得ないので。）

ソートの速度

データ一覧（比較用の値が重複しない）をソートする必要がある場合、一旦リストに入れてからCollections#sort()を呼ぶ方法と、TreeSetを使ってソートしながらデータ一覧を作成する方法が考えられる。[2009-03-25]
（重複するデータがある場合、TreeSetは使えない。Collections#sort()は重複する箇所は元のソート順が保証される）

List data = new ArrayList();
data.add(〜);

List list = new ArrayList(data);

int size = data.size();
List list = new ArrayList(size);
for (int j = 0; j < size; j++) {
  list.add(data.get(j));
}

int size = data.size();
Set list = new TreeSet();
for (int j = 0; j < size; j++) {
  list.add(data.get(j));
}

Set list = new TreeSet(data);

Collections.sort(list);

int size = list.size();
for (int j = 0; j < size; j++) {
   Object obj = list.get(j);
// System.out.println(obj);
}

for (Iterator j = list.iterator();
 j.hasNext();) {
   Object obj = j.next();
// System.out.println(obj);
}

for (Iterator j = list.iterator();
 j.hasNext();) {
   Object obj = j.next();
// System.out.println(obj);
}

データは別のArrayListを用意し、そこからソート用のArrayList/TreeSetを作り、ループしてデータを1つずつ取り出す一連の処理を行う。
ソート用のインスタンス生成からデータを取り出すまでの時間を計測した。

インスタンス生成も「コンストラクターにデータのArrayListを直接渡す方式」と「デフォルトインスタンスだけ作って自分でデータを追加していく方式」の二種類考えられるが、ArrayListとTreeSetでは、それぞれ速い方式が違う。TreeSetは速い方だけ測定した。
ソート後のデータ出力は、下記のsort(速)もsort(遅)もRandomAccess方式（速い方）を使用した。

JDK1.4では、sort(速)（ArrayListをコンストラクターから作る方式のCollections#sort()）が明らかに速い。
ただし、実際の使用用途から言って、ArrayListからArrayListを作り直すことはたぶんあまり無いので、sort(遅)の方が普通に出てくるパターンかもしれない。（ただし、元データがArrayList以外でも、自分で1個ずつadd()するよりはコンストラクターに任せる方が速い可能性はある）
それでも、JDK1.4ではsort()の方がTreeSetより（ほぼ全パターンにわたって）速いが。

JDK1.5や1.6では、データ数が少ない場合はTreeSetの方が速い。
JDK1.5では、データ数が10個程度以上なら、Collections#sort()を使う方が速そうだ。
JDK1.6ではTreeSetがだいぶ優秀になっているみたいなので、どれくらいの個数で見切るか（sort()とTreeSetのどちらを使うか）を判断するのはちょっと難しそう。