Java魂4章
まだまだ続く、Java魂の4章、「コレクション」のおかしな部分の紹介。
まずは、4.2.2 O記法(Big O Notation)より。
リストに100人の人が含まれていると、最悪の場合には1人の人を探すのに99回チェックを実行する必要があります。
4.2.2 O記法(Big O Notation)より
検索対象の人がリストに含まれているかどうかがわからない場合、100回のチェックが必要である。
一般に、O(n)よりも大きなアルゴリズムは実際の問題の解決策としては適していません。
4.2.2 O記法(Big O Notation)より
知らなかった！クイックソートやマージソートなんて使わずに、ビンソートや分布数え上げソートを常に使えと、そういいたいのか。それこそ実際の問題の解決策としては適してないと思うけどなぁ。それとも、ソートは一般的な問題ではないと考えているのだろうか？
次は4.2.3.1のVectorの説明。
Vectorはスレッドセーフになるように設計されているので、コード内にsynchronizedブロックが多数存在します。これにより、複数のスレッドがVectorを安全に使用できるようになりますが、性能が著しく悪化します。
4.2.3.1 java.util.Vectorより
間違ってはいない。間違ってはいないが、もちろん安全に使用できるのは、Vectorが用意しているメソッド単位であって、メソッドを組み合わせた場合はクライアントサイドロックが必要である。
続いて4.2.3.3 java.util.LinkedList。
このノードベースの構造により、LinkedList内の要素の挿入や削除が簡単になります。リストでは、ノードを生成し、前と次のオブジェクトへの参照を書き換えるだけでよいのです。ありがたいことに参照をコピーしたり、その他のコストのかかる処理を実行したりする必要はありません。
4.2.3.3 java.util.LinkedListより
そうだといいんだけどね。以下は最後の要素に値を追加するパフォーマンスを計測するテストだ*1。
import java.util.*; public class ListTest { private static final int SIZE = 1000000; private static long testList(List<Integer> list) { long start = System.currentTimeMillis(); for (int i = 0; i < SIZE; i++) { list.add(i); } return System.currentTimeMillis() - start; } private static long testDeque(Deque<Integer> deq) { long start = System.currentTimeMillis(); for (int i = 0; i < SIZE; i++) { deq.offerLast(i); } return System.currentTimeMillis() - start; } public static void main(String[] args) { long time = testList(new LinkedList<Integer>()); //long time = testDeque(new LinkedList<Integer>()); //long time = testList(new ArrayList<Integer>()); //long time = testList(new ArrayList<Integer>(SIZE)); //long time = testList(new ArrayList<Integer>(SIZE / 2 - 1)); //long time = testList(new Vector<Integer>()); //long time = testList(new Vector<Integer>(SIZE)); //long time = testList(new Vector<Integer>(SIZE / 2 - 1)); System.out.println(time + "ms."); } }
このテストの結果、以下のようになった。
| LinkedList | 617ms |
|---|---|
| LinkedList as Deque | 615ms |
| ArrayList | 317ms |
| ArrayList(SIZE) | 233ms |
| ArrayList(SIZE / 2 - 1) | 354ms |
| Vector | 457ms |
| Vector(SIZE) | 278ms |
| Vector(SIZE / 2 - 1) | 383ms |
見てわかるとおり、LinkedListは一番遅い結果に終わっている。これは、LinkedListの最後尾に追加するときに、最初の要素からたどる必要があるからだ*2。この操作はもちろんO(N)であり、「その他のコストのかかる処理」に相当する。この結果から、
このクラス*3は、ソートや、挿入と削除を頻繁に行うような処理に理想的です。
4.2.3.3 java.util.LinkedListより
というのは言い過ぎで、正しくは、「先頭付近で挿入と削除を頻繁に行うような処理に理想的です。」となる。(Javaの)LinkedListは実は意外に適用できる範囲は狭いのだ。正しくはコメント欄参照。
以降、読む気がなくなったのでこの章はこれで終わり。なんだか悲しくなってきた。
