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万件でもやりたかったのですが実行時間がかかりすぎるので断念しました
