LinkedListとArrayListの性能差を検証してみた
こんにちは！
前回に続き、LinkedListとArrayListの使い分けについて考察していきます。
Listがそもそもなんだかよくわからん！という方はこちらをどうぞ。
前回ご紹介した通り、JavaのListにはいくつかの種類があります。
Java APIドキュメントによれば、
Listインタフェースの既知の実装クラスは
AbstractList, AbstractSequentialList, ArrayList, AttributeList, CopyOnWriteArrayList, LinkedList, RoleList, RoleUnresolvedList, Stack, Vector
とありますので、他にも幾つかあることがわかります。
その中でも、ArrayListやLinkedListは使用頻度が高いので、今回ピックアップしてご紹介します。
使い方の違い
特にありません。 同一のインタフェースであるListを実装していますので、インスタンスの生成方法や呼び出せるメソッドに差はほぼありません。
内部の仕組みの違い
使い方に違いが無いということは、内部的に何かが違うということなのでしょう。 一般的には、以下のような違いがあると言われています。
ArrayList
- ランダムアクセスに強い（例えば、「10番目の要素を取得」する等）
- Listの途中にオブジェクトを挿入し、以後の要素を右にズラしたり、特定の要素を削除するような作業に弱い
2つ目のポイントについては、
全要素に通し番号を振って管理しているため、途中に挿入したり削除したりすると番号がずれてしまい、
以後の番号を振り直す作業が必要になるためだと思われます。
LinkedList
- ランダムアクセスに弱い
- Listの途中への挿入・削除に強い
1つ目のポイントに関しては、
全要素に通し番号を振っておらず、各要素が自分の次の要素のみを把握する（リンクしている）Listであるため、
List全体に対して「n番目の要素」と言っても、先頭から数えて行く必要があるためだと思われます。
2つめに関しても同様に、
全要素に通し番号を振っておらず、各要素が自分の次の要素のみを把握しているため、
途中にオブジェクトを挿入したとしても、隣接している要素に影響が及ぶだけで、
配列全体の通し番号を変更する必要が無いからだと思われます。
検証① ランダムアクセス（特定の位置からオブジェクトを取得する）
では、ランダムアクセスで検証してみたいと思います。
巨大なListの作成
両Listは、性能面で差が出るとは言いつつも微差なので、 大量に処理させることで違いをわかりやすくしたいと思います。
では、巨大なListを作ってみます。 データ型は、よく使いそうなStringにしてみます。
List<String> sampleArrayList = new ArrayList<>(); List<String> sampleLinkedList = new LinkedList<>(); for(int i = 0; int < 10000000; i++){ sampleArrayList.add("Some Object"); } for(int i = 0; int < 10000000; i++){ sampleLinkedList.add("Some Object"); }
はい、1000万の要素を持つListが2つできました。
特定の要素を取り出す
では、特定の要素を取り出すコードを書いてみます。
こちらも、やはり100回くらいやった方が良いと思うので、繰り返し処理などを用いていきます。
あとは、パフォーマンス測定のためにSystem.nanoTime()メソッドを利用して
処理前、処理後のシステム時間を記録し、差を出すことで実際にかかった時間を測定していきます。
ArrayListから行きます。
//開始時間取得 long timeBefore = System.nanoTime(); //適当な要素を100回取得する for(int i = 0; i < 100; i++){ sampleArrayList.get((int)(Math.random() * 10000000)); } //終了時間を取得 long timeAfter = System.nanoTime(); //終了時間 - 開始時間を表示 System.out.println(timeAfter - timeBefore);
ブレもあると思うので、3回程実行してみました。
ナノ秒だとわかりづらいので、ミリ秒に変換しますね。
1回目：0.72ミリ秒
2回目：0.97ミリ秒
3回目：0.82ミリ秒
いずれも、1ミリ秒以下です。
では、次にLinkedListで試します。
//開始時間取得 long timeBefore = System.nanoTime(); //適当な要素を100回取得する for(int i = 0; i < 100; i++){ sampleLinkedList.get((int)(Math.random() * 10000000)); } //終了時間を取得 long timeAfter = System.nanoTime(); //終了時間 - 開始時間を表示 System.out.println(timeAfter - timeBefore);
1回目：1067ミリ秒
2回目：1041ミリ秒
3回目：979ミリ秒
大体、1秒前後かかっていますね。
というわけで、検証①の「ランダムアクセス」に関しては、明らかにArrayListのほうが高速な様子です。
「検索結果一覧表示」などは、ArrayListが良さそうですね。
検証② Listの途中への要素挿入
では、Listの途中に要素を挿入するときのことを想定して検証してみましょう。 一応ランダムアクセスは発生しますが、ArrayListでは通し番号を再度振り直す必要がでてきますので、 性能面ではLinkedListのほうが上回るかあるいは同等、と予想できます。
とは言いつつも、仮に例えばArrayListの終端に近いような位置へ挿入すると 通し番号の振り直し回数も減りますので、ArrayListのほうが上回る可能性もあります。
巨大なListの作成
検証①と同じです。
List<String> sampleArrayList = new ArrayList<>(); List<String> sampleLinkedList = new LinkedList<>(); for(int i = 0; int < 10000000; i++){ sampleArrayList.add("Some Object"); } for(int i = 0; int < 10000000; i++){ sampleLinkedList.add("Some Object"); }
適当な位置に新しいオブジェクトを挿入する
では、ArrayListから行きましょう。
//開始時間取得 long timeBefore = System.nanoTime(); //適当な位置に適当な要素を100回挿入する for(int i = 0; i < 100; i++){ sampleArrayList.add((int)(Math.random() * 10000000), "Another Object"); } //終了時間を取得 long timeAfter = System.nanoTime(); //終了時間 - 開始時間を表示 System.out.println(timeAfter - timeBefore);
1回目：3529ミリ秒
2回目：3315ミリ秒
3回目：2832ミリ秒
約3秒という結果になりました。
ちなみに、ランダムな位置ではなく、Listの終端に近い位置（9,999,995等）に挿入してみると 0.05～0.1ミリ秒程度になりましたので、やはり挿入位置が先頭に近いほどArrayListは遅くなるようです。
では、LinkedListで試して行きましょう。
//開始時間取得 long timeBefore = System.nanoTime(); //適当な位置に適当な要素を100回挿入する for(int i = 0; i < 100; i++){ sampleLinkedList.add((int)(Math.random() * 10000000), "Another Object"); } //終了時間を取得 long timeAfter = System.nanoTime(); //終了時間 - 開始時間を表示 System.out.println(timeAfter - timeBefore);
1回目：1027ミリ秒
2回目：995ミリ秒
3回目：1035ミリ秒
大体1秒前後でした。 こちらに関しては、挿入位置を終端寄りにしても、大きな差は出ませんでした。
というわけで、待ち行列などを管理していて、割り込みなどが多発するケースでは LinkedListが適切なのではないかと思います。
まとめ
いずれにせよ、処理する件数が多くないなら微差ですが
不特定多数のリクエストを捌かなければいけないWebサーバなどでは有用かもしれません。
長くなりましたが、今回はこの辺で。
