JavaのListについて

More than 3 years have passed since last update.


この記事の目的

Javaには便利に使えるコレクションがたくさんあります。ListやSetなんかがその代表だと思いますが、それぞれの実装によって、挿入は早いけどアクセスは遅いなど、いろいろと特徴があると思います。この記事ではJavaの実装を見ながら、そこらへんの基本的なところをおさらいしようと思います。

今回はコレクションでも多分最もよく使うであろうList系、特にArrayListとLinkedListに絞って調べていきます。

ソースコードは

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/ArrayList.java#ArrayList

および

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/LinkedList.java#LinkedList.Node

から引用してます。


ArrayListとLinkedListの違い

中でのデータの持ち方が違います。

ArrayListは内部にObjectの配列を持っていて、要素はそこに格納されます。LinkedListは要素をNodeに格納し、それを連結することで順序付きのコレクションを実現しています。

ArrayListは


ArrayList.java(134行目あたり)

 transient Object[] elementData; // non-private to simplify nested class access


っていうのが要素の実態で、この配列に対して


ArrayList.java(457行目あたり)

public boolean add(E e) {

ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}


ArrayList.java(428行目あたり)

public E get(int index) {

rangeCheck(index);

return elementData(index);
}


こんな感じでaddしたりgetしたりしてます。

add内で呼ばれているensureCapacityInternalで格納している配列のサイズをチェックして、領域を超えるようだったら更にgrowメソッドを呼び出して、配列を拡張しています。デフォルトでは既存のサイズの1.5倍になるみたいです。

一方、LinkedListは内部クラスでこういうのを持ってます。


LinkedList.java(970行目あたり)

private static class Node<E> {

E item;
Node<E> next;
Node<E> prev;

Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}


このノードは次のノードへの参照と前のノードへの参照を保持してます。

で、LinkedList自体はNodeのfirstとlastを保持してます。

こういう感じで頭、もしくはおしりの方から目的のindexまでノードをたって行く形ですね。


LinkedList.java(566行目あたり)

 Node<E> node(int index) {

// assert isElementIndex(index);

if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}


こういう特性を持っているので、一般的にアクセス時間はArrayListの方が圧倒的に早いです。ここらへんはArrayListがマーカーインタフェースでRandomAccessを持ってるあたり、明示的ですね。

ただし、ArrayListはリストの途中に要素を挿入する場合、配列をSystem.arraycopyを用いて配列を複製します。なので、そういう時はLinkedListを使いましょう。


for, 拡張for, foreachなど

Listの要素をすべてたどるのによくforとか使うけど、書き方がいろいろありますよね。ざっと見たところ、下の4つに分けられると思います。

1: for文

for(int i=0; i<list.size(); i++) {

list.get(i);
}

2: Iterator

Iterator itr = list.iterator();

while(itr.hasNext()){
itr.next();
}

3: 拡張for文

for(Object o : list) {

}

4: foreach (Java8から)

list.forEach(o -> { });

今回はこの4つの実装、パフォーマンスについても調べました。

1については今更言う必要ないと思います。

2のIteratorの実装ですが、大体はIteratorをimplementsした内部クラスを持っていて、その中で現在位置を保持するcursorを管理してるみたいです。特に、LinkedListの場合はgetで要素にアクセスしようとした場合、リストの先頭(もしくは最後尾)から探索を開始するので、このIteratorを使ったアクセスのほうが圧倒的に早いです。

3のいわゆる拡張for文ですが、]この記事によると、これはこんな風に動作するらしいです。

for(Object o : list) {

System.out.println(o.toString());
}

これが

Object o;

for(Iterator it = list.iterator(); it.hasNext(); System.out.println(o.toString()) {
o = it.next();
}

こうなる。

つまり、内部的にIteratorを呼び出してくれています。拡張for文を使うとIteratorを使った呼び出しが簡単に書けるようになります。

4のforEach。これはjava8から追加された書式です。引数にConsumerを受け取って、各要素に適用していきます。

このforEachですが、そもそもはIterableに実装されてます。


Iterable.java(72行目くらい)

default void forEach(Consumer<? super T> action) {

Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}

つまり、デフォルトでは普通に拡張for文使ってますね。

ちなみに、ArrayListではこのforEachがOverrideされて、以下のようになってます。


ArrayList.java(1241行目くらい)

    @Override

public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}

並列アクセスの例外処理系を除くと、1の普通のfor文で要素にアクセスする方法をとってることがわかります。ArrayListはRandomAccessなので、Iteratorを使って要素にアクセスするよりも普通にgetを使ったほうがアクセスが早いので、こういった実装になってるんだと思います。

最後に、せっかくなのでこの4つの方法についてパフォーマンスの計測をしました。対象はJava8のLinkedListとArrayList。検証環境はMacBook Air(11inch) 1.7GHz Core i7 / 8GB RAMです。長さを1000に固定したリストについて、それぞれ全要素へのアクセスを30000回繰り返し、その速度を測定しています。

結果は以下のとおりです。

LinkedList
ArrayList

for
15020ms
25ms

Iterator
115ms
27ms

拡張for
121ms
22ms

forEach
142ms
101ms

概ね想定通りの値に落ち着いてると思います。Iteratorと拡張forの値がずれてるのが気になりますが、ここらへんは誤差でしょうか??forEachについてはLambdaを呼び出すオーバーヘッドと捉えていいんでしょうか。こういった値になりました。


コメントを頂いたので追記。

確かにこれだとLinkedList使えねー、てなりますね。でもArrayListよりもLinkedListが有利なケースはあります。それがリストの途中に要素を挿入するケースですね。

というわけで、リストの途中に要素を挿入し、それを30000回繰り返してパフォーマンスも計測してみました。

結果は以下のとおりです。

LinkedList
ArrayList

7ms
88ms

というわけで、圧倒的にLinkedListの方が早いという結果になりました。


まとめ

ArrayListとLinkedList、Javaで最も使う2つのリストについて、基本的な特性を調べました。ついでに、for, 拡張forなどのイテレーションの方法についてもパフォーマンスの計測などを行って、その特性を調べました。

指摘、コメントなどなどありましたら、ぜひおねがいします!