はじめに
昔書いた記事を眺めていたら、「JavaでよくつかうCollection実装クラスの仕組みと特性」の記事が、「collection型のクラスであるlinkedListに関するランダムアクセスの遅さという課題への取り組み」という記事で参考にされていました。ありがとうございます！
こちらの記事では、LinkedListで作成した処理について、for文と拡張for文で実行時間を比較しており、拡張for文のほうが圧倒的に早いという結果が出ています。
今回は、この拡張for文についてなぜ普通のfor文よりも高速か、というところを解説していきたいと思います。
拡張for文とは何ぞや？
そもそも拡張for文とは何か？
コレクション(ListやSetなど)の要素を繰り返し取り出して、何かしらの処理を行うときなどに使用する構文です。
例えば、Listに格納された数値の総和を取るために、for文と拡張for文ではそれぞれ下記のように記述します。
List<Integer> list = Arrays.asList(1,3,5,7);
for(int i = 0;i < list.size(); i++){
sum += list.get(i);
}
List<Integer> list = Arrays.asList(1, 3, 5, 7);
for(Integer i: list){
sum += i;
}
つまり、拡張for文は
for(要素の型 要素を入れる変数: コレクションの変数){
処理(要素が入った変数を処理に使用できる)
}
という構文になっていることがわかります。
普通のfor文と比べてシンプルな記述になっていますね。
拡張for文は何をやっているのか？
拡張for文が内部的にどういう動きをしているか、Javaのドキュメントを読んでみましょう。
ちなみに拡張for文と呼ばれることが多いですが、実はJavaのドキュメントではFor-Eachループという項目になっています。
これによると、下記2つのコードは等価であるとのこと。
その上で、拡張for文のほうがiterator変数を扱わないことから複雑性やエラーの危険性が排除されるのでより推奨されます。
List<Integer> list = Arrays.asList(1, 3, 5, 7);
for(Integer i: list){
sum += i;
}
List<Integer> list = Arrays.asList(1, 3, 5, 7);
for(Iterator<Integer> i = list.iterator(); i.hasNext();){
sum += i;
}
つまり、拡張for文は内部的にはiteratorによる反復処理を行っているということがわかります。
なぜLinkedListだと拡張for文が格段に高速なのか？
LinkedListの実装を考えてみましょう。
詳細な説明は「JavaでよくつかうCollection実装クラスの仕組みと特性」に記載がありますが、LinkedListは下図の通り、ノードが連結した形の構造になっています(本来は前後にリンクがある二重リンクリストですが、話を簡単にするために片方だけのリンクを持つ構造として説明しています)。
そのため、ノード3を参照するときには、ルートから始まり、ノード1、ノード2、ノード3と順番にノードをたどることになります。
ここで、for文を使った繰り返しで全要素にを参照する場合を考えると、それぞれのノードを参照するときの処理は下記のようになります。
- ノード1：ルート⇒ノード1
- ノード2：ルート⇒ノード1⇒ノード2
- ノード3：ルート⇒ノード1⇒ノード2⇒ノード3
この場合、ノード3を参照するときに再度ルートから順番に辿ることになってしまい、効率が悪くなります。
そこで、LinkedListのIteratorでは、現在位置を保存することで、これを解消して効率よく内部の要素を返しています。
上述したように、拡張for文ではIteratorを使っているので、結果として拡張for文を使うことで効率の良い反復処理が可能になった、ということになります。
拡張for文とfor文のどちらを使うべきか？
Iteratorは効率的な反復処理を提供するという前提に基づくならば、基本的に拡張for文を使うことで常に効率のいい反復処理が実行できます。
単純な配列の反復処理では、for文のほうが高速な場合もありますが、ほんの数ms程度なので変更に強いコードにするためにも拡張for文を使いましょう。