といっても、そんなに小難しい話をするつもりはなくて

JavaのCollectionインタフェースに関して、各操作についてどの程度パフォーマンスが違うか測ってみた、というだけです。いつも無意識にListならArrayList、MapならHashMapを選んでしまう自分への警鐘ということで。

まずはListインタフェース。測定対象は以下。CopyOnWriteArraySetとか、この実験やろうとして初めて知った件。

List vector = new Vector();
List array = new ArrayList();
List linked = new LinkedList();
List stack = new Stack();
Set tree = new TreeSet();
Set hashset = new HashSet();
Set linkedset = new LinkedHashSet();
Set copy = new CopyOnWriteArraySet();

上記に対する計測対象の操作は以下の通り

  • 操作A: 50000個の要素を1回ずつput（要素はIntegerで0〜49999）
  • 操作B: 操作A後のものに対してイテレータを最初から最後まで回す
  • 操作C: 操作A後のものに対して対象をランダムに5000回containsを実行
  • 操作D: 操作A後のものに対して対象をランダムに5000回removeを実行

で、結果は以下の通り（単位はms、小数点四捨五入）。

Listインタフェース Setインタフェース
Vector ArrayList Linked
List		 Stack Tree
Set		 Hash
Set		 Linked
HashSet		 CopyOn
WriteArraySet
操作A 16 19 19 7 123 76 32 13589
操作B 20 18 21 25 20 14 7 3
操作C 367 357 1374 437 8 3 2 424
操作D 469 521 1940 461 25 5 12 2550

今回の目的は絶対値の計測ではなく実装の変化による速度の違いなので、縦の列でなく横の行における相対的な違いだけで見てもらいたい（速度自体はマシンによって変わるから）のですけど、かなりはっきりと違いが出ました。
ArrayListよりVectorの方が性能がよく見えるのはシングルスレッドで各操作をやっているからであって、これがマルチスレッドになるときっと変わってくるんでしょうね（Vectorは完全同期を取るので待ちが発生するはず）。
ListとSetでは、ランダムアクセス系でここまで顕著に差が出るとは。要件として重複があり得るかあり得ないかの確認はかなり重要、という訳ですね。HashSetよりLinkedHashSetのほうが数字がいいのがなんかおかしいような気もしますが。誤差の範囲かな。。
などなど、定量化して改めて設計の重要さを認識。

Mapインタフェースに関してはまた後日。。

diary, technology

2010/06/17

コメントする