投稿者:

Collectionインターフェースの実装による速度の違い 1

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

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インタフェースに関してはまた後日。。

広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中