Java : Listの使い方

プログラミング

先日（[id:lethevert:20060211:p2]）、ArrayListが使いたい場合でも、

List list = new ArrayList();

としておくのが作法であり、それは、後から実装を交換する可能性があるからだ、ということを書いたが、それがどういうことかということを説明する。

規模によって変わる特性要求

ArrayListは配列と同じ特性を持っている。つまり、

  • データは連続領域にとられる
  • インデックスにより直接アクセスする

通常、ランダムアクセスが必要なリストを使う場合は、ArrayListを使っておくべきだ。また、シーケンシャルアクセスのみの場合でも、メモリの先読みが効くので、ArrayListの方が望ましい。
しかし、要素数がある程度以上になると、ArrayListが最適とは限らなくなる。というのは、要素数の大きい配列は、長い連続領域をメモリに確保しなければならないため、メモリ割り当てのコストが増大してくるからだ。
たとえば、100万要素をもつ配列の場合、ポインタサイズが4byteならば、約4Mbyteの連続領域をメモリに確保しなければいけないことになる。通常のオブジェクトのサイズが十数byte〜数十byteであることを考えると、4Mbyteの大きさは際立っている。
100万要素は極端な例だが、規模の増大に伴う場合のメモリ割り当てコストの増加は、実装を交換する動機には十分なりうる。

用途によって変わる特性要求（１）

ArrayListは、以下の２つの大きな弱点を持っている。

  • 挿入の際に、挿入された要素以降のデータのコピーが発生する
  • 容量を超えたときに、メモリの再割り当てと、全要素のコピーが発生する

このことは、要素がソートされたリストや、要素が漸次的に増加するリストには、ArrayListは向いていないことを示している。
特に、初期設計の段階では、要素をソートしていなくても、実装を進めるにつれて、ソートされている方がよいということになって、そのように実装を変更することは、考えられないことではない。そのような場合、当初ArrayListで実装していたものを、別のListに交換することは、十分に起こりうる。

用途によって変わる特性要求（２）

ArrayListは同期化されていない。このことは、マルチスレッドな状況では、ArrayListは再現性の低いバグを生み出す可能性があることを示している。
初期設計の段階で、スレッドセーフであることは要求されていなかったが、実装を進めるにつれてスレッドセーフであることが必要であることが判明するということは、考えられないことではない。Javaの標準ライブラリにおいて、スレッドセーフなArrayListの代替は以下の２つがある。いずれもListインターフェースを実装している。

  • java.util.Collections#synchronizedList()
  • java.util.concurrent.CopyOnWriteArrayList

シーケンシャルアクセスの書き方について

以上見たように、後から実装を交換する必要が出てくることは十分にありうると考えて、初期コードは書いておくのが、複雑さと戦うプログラマの基本的な知恵だ。
だから、たとえば、シーケンシャルアクセスを書くならば、迷わずに下のように書くべきだ。（あるいは、Java 5で導入された拡張for文を使うべきだ。）

for(Iterator itr = list.iterator(); itr.hasNext();) {
  ...
}

これを、実装がArrayListであるからといって、

int size = list.size();
for(int i=0; i<size; ++i) {
  Object o = list.get(i);
  ...
}

と書くのは、非常に貧乏くさい。高々Iteratorの生成コストをケチって、普遍性を犠牲にするなんて、プログラマのやるべきことではない。
また、さらに言えば、シーケンシャルアクセスしかしないのなら、ListではなくCollectionで宣言しておくべきだ。

富豪的プログラミング

最後の方の話は、要するに富豪的プログラミングのことだ。
パフォーマンスチューニングというのは、パフォーマンスデータを確認して、ボトルネックを確認して行うべきことで、そういう場合、データ構造の選択に間違いがあることの方が圧倒的に多いのだから、始めからデータ構造を変更しやすいようにしておくのが、プログラマとしてのセンスなのだ。