Javaを結構勉強している人は間違いがないかご確認下さい（笑
今回の日記では、ArrayListとLinkedListの使い分けに絡めて、for文と拡張for文およびIteratorではどちらの方がアクセス速度が早いのか、といったところです。
さて、私はこの2つのクラスを今までは、何となくスタックの機能使いたいからLinkedListで、それ以外はArrayListでいいかなと言った感じで使ってました。
はい、ダメダメですね。
何がダメかと言うと、次の特徴を見れば分かると思います。
2つのリストにおける最大の特徴
public class ArrayListextends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable
public class LinkedList
extends AbstractSequentialList
implements List, Deque , Cloneable, java.io.Serializable
即ち、以下のようになっています。
| 追加・削除 | アクセス方法 | |
|---|---|---|
| LinkedList | ポインタのnext,previousを変更 | シーケンシャルアクセス |
| ArrayList | 新しく配列を作る | ランダムアクセス |
シーケンシャルアクセスはその名の通り順次アクセス。
Listの中を1つ1つポインタを経由してアクセスしていきます。
逆にRandomAccesは指定したインデックス分だけポインタを進めて直接アクセスできます。
語弊を恐れずに例えて言うなら、
シーケンシャルアクセスは各駅停車で目的の駅に向かうのに対して、
ランダムアクセスは自分の好きな駅に直接止まってもらう形です。
ですのでfor文によるアクセス結果は容易に想像ができると思います。
拡張for文とIteratorは、ほぼ同じような実装で、違いはfor文の中でコレクションクラスをいじれるかどうか、と言った所です。(主に要素のremove)
ソースはこちら。
実行結果は下記に表示。
/**
* LinkedListとArrayListの実行アクセス速度を比較.
* @author Takuya Iida
*/
public class ListTest {
public static final int MAX_LOOP = 50000;
public static void main(String args[]) {
//Initialize
List testArrayList = new ArrayList();
List testLinkedList = new LinkedList();
System.out.println("-----ArrayList-----");
testList(testArrayList);
System.out.println();
System.out.println("-----LinkedList-----");
testList(testLinkedList);
System.out.println();
}
public static void testList(List testList) {
//計測時間用変数
long start, end;
//Initialize
for (int i = 0; i < MAX_LOOP; i++) {
testList.add(i);
}
//通常のfor文
start = System.currentTimeMillis();
for (int i = 0; i < MAX_LOOP; i++) {
testList.get(i);
}
end = System.currentTimeMillis();
System.out.println("for文 = " + (end - start));
//拡張for文
start = System.currentTimeMillis();
for (int i : testList) {
}
end = System.currentTimeMillis();
System.out.println("拡張for文 -> " + (end - start));
//Iterator
start = System.currentTimeMillis();
for (Iterator it = testList.iterator(); it.hasNext();) {
it.next();
}
end = System.currentTimeMillis();
System.out.println("Iterator -> " + (end - start));
}
}
実行結果
-----ArrayList
for文 -> 5
拡張for文 -> 12
Iterator -> 7
-----LinkedList
for文 -> 1606
拡張for文 -> 11
Iterator -> 6
圧倒的速さ、拡張for文、Iterator。
なぜこうなったかを説明します。
for文の場合、getでアクセスしていきますが、
ArrayListはランダムアクセスできるので、指定されたインデックスの駅に毎回直接向かえます。
LinkedListの場合はシーケンシャルアクセスなので、毎回始発駅から目的地に向かいます。
非常に無駄ですね。
要素数が5個の場合、アクセスのイメージとしては
ArrayListは[1, 2, 3, 4, 5]とアクセスできるのに対して、
LinkedListは[1, 1→2, 1→2→3, 1→2→3→4, 1→2→3→4→5]となります。
よってリスト数が多くなればなるほど、ランダムアクセスで探索する場合、LinkedListは遅くなってしまいます。
※ただし、先ほどの例は正確ではないです。
最初の要素は当然ですが、最後の要素にもアクセスする場合、実行速度が早かったためです。
逆に真ん中あたりの要素へのアクセスは遅くなりました。
そういったことから、内部的に「最初から」 or 「最後から」のどっちでアクセスする方が早いのか判断してアクセスしていると思われます。
対して、拡張for文およびIteratorは、アクセスの度に始発駅から出発せずに、1つの各駅停車で乗り降りするだけで済みます。
「今、どの駅にいるか」というのを記憶しているため、LinkedListではアクセス速度が早くなったといえます。
講師の松本さんよりコメントを頂きました。
for文と拡張for文及びIteratorとの実行速度の違いは、その呼び出しメソッドの数に関係があるとのこと。
確かによくよく考えてみるとfor文ではインクリメントしてアクセスするだけに対して、Iterator(拡張for文)ではhasNextやnextメソッドが頻繁に呼び出されてますね。なるほどなるほど。
ですので、ArrayListではfor文の方が若干だけアクセスが早いです。
だからと言ってfor文を使えばいいと言うわけではないので注意。
なぜなら、個人的に拡張for文の方が可読性はいいし、多態性を考えると拡張for文やIteratorでアクセスする方がクラスの違いに囚われないので。
これに関してはよく分かりません。
同様にコメントを頂きました。
拡張for文はコンパイル時にIterator形式に変換されるので実行効率は全く同じである。とのこと。
ではどこでその差がでたのかと言うと…オートボクシングでした。
完全に盲点でしたが、拡張for文において
for(int i : testList)という記述ではアンボクシングされてます。
それに対してIteratorではit.next();で要素を得ているだけですのでアンボクシングはされていません。
そこに実行速度の差が生じていると仮定し、int i = it.next();でアンボクシングを行わせると大体3~5msの差に縮まりました。
そして最後に最も重要な違いである、要素の削除、追加については、リスト構造のLinkedListが早く、配列形式のArrayListが遅いです。
リスト構造ということは、すなわちリストにNextやPreviousといった参照を持っているので、その参照を書き換えるだけで済みます。
対して配列形式の場合は、削除・挿入すると1つずつ要素をズラして新しい配列を作るためコストが非常に高いです。
ただし、最後に要素を追加する場合、ArrayListでは事前に多めに配列を確保しているので、そこに新しい要素を加えるだけでいいのでそれほど遅くはありません。
ある程度の要素数がある状態で、配列の最初に新しい要素を加える場合が最もコストが高くなるでしょう。
要素の追加削除が頻繁な場合はLinkedList。
それ以外はArrayListの方がいいのかな。と思いました。
参考文献：http://d.hatena.ne.jp/perlcodesample/20080808/1218261466