読者です 読者をやめる 読者になる 読者になる

かまたま日記3

プログラミングメイン、たまに日常

ArrayListとLinkedListのパフォーマンスチェック

Listの2大実装であるArrayListとLinkedList。
その昔どのような用途で使うのがいいかを調べましたが、実際のパフォーマンスはどうなのかを調べてみました。

調査方法

二つのListに対して以下の順番で処理をしていきます。

順番 処理名 処理内容
1 addSequence 指定した回数listにadd(Integer)する
2 iterator iteratorを使ってリストを展開し、入っている数値の総和を計算する
3 indexOf ランダムな数値に対してindex(Integer)を3000回行う
4 lastIndexOf ランダムな数値に対してlastIndexOf(Integer)を3000回行う
5 addRandom ランダムなindex番号に対してadd(index, Integer)を3000回行う
6 getRandom ランダムなindex番号に対してget(index)を3000回行う
7 removeRandom ランダムなindex番号に対してremove(index)を3000回行う
8 removeSequence リストのサイズ分だけremove(0)を行う

最初にaddSequenceする回数を以下の順番で増やしていきます*1

  • 1000件
  • 10000件
  • 100000件

結果(5回の平均値、単位はすべてミリ秒)

ArrayList

処理名 1000件 10000件 100000件
addSequence 0.14 0.16 4.56
iterator 0.38 0.73 0.21
indexOf 1.91 62.2 6624
lastIndexOf 1.68 62.3 6628
addRandom 3.93 5.12 51.9
getRandom 3.12 0.04 0.04
removeRandom 4.96 5.23 51.6
removeSequence 6.66 12.7 1740

LinkedList

処理名 1000件 10000件 100000件
addSequence 0.35 0.67 1.67
iterator 0.29 0.52 0.43
indexOf 2.10 159 16273
lastIndexOf 1.95 151 16639
addRandom 5.37 26.8 206
getRandom 4.55 43.3 231
removeRandom 5.09 37.5 231
removeSequence 0.18 0.16 0.77

やはりランダムアクセス系の処理が発生する処理はArrayListが、順番に処理する処理はLinkedListの方が早いようです。
特にArrayListのgetRandomとLinkedListのremoveSequenceは件数がスケールしてもほぼ処理速度が変わらず、もう一方のリストとの速度差がはっきり出ています。
こういった処理を行う場合はそれぞれのListを選択するのが良いようです。

検証コード

Gistに上げています。
https://gist.github.com/3947864

*1:100万件でもやりたかったのですが実行時間がかかりすぎるので断念しました