ArrayListのコンストラクタに初期容量を指定することで要素の追加処理を高速化

javaのArrayListのコンストラクタにはオーバーロードで幾つかの種類がありますが、その一つに以下のようなものがあります。

ArrayList(int initialCapacity)
指定された初期サイズで空のリストを作成します。
Java 2 Platform SE 1.3: クラス ArrayList

ArrayListは動的に容量を確保しますが、そのメモリ割り当て処理はCPUにそれなりの負荷を与えます。そこで、予め格納する容量が分かっていればコンストラクタの引数で初期容量を指定することで、その負荷の掛かる処理を事前に省くことが出来、その結果、処理時間の短縮につながります。

ちなみに、このint initialCapacityの容量の単位はコレクションの要素数です(2008/3/7修正)。

以下に初期容量を指定したときとしないときのでの処理時間を計るJavaのソースコードを示します。

入力ファイルは日本語単語405,000語で4898304Byteです。

結果は、

mlistに対して初期容量を指定しない場合:17ms
mlistに対して初期容量を指定した 場合:8ms

となり、今回の場合は処理時間を1/2に短縮できていることが分かりました。
ちなみに、ArrayListのメモリ動的割り当て容量は、現在の容量の1.5倍のようです。

int newCapacity = (oldCapacity * 3)/2 + 1;
ArrayList#ensureCapacityメソッド内の一文 – ArrayList.java 1.56 06/04/21

参考にしたサイト

  • Java 入門 | ArrayList クラス

追記(2008/3/7):

1.コンストラクタでインスタンス容量を指定するものとして、StringBufferクラスがあります。これも、

のように指定します。

これによって、append()やinsert()によって予め割り当てられたバッファを越す際に呼び出されるメモリ動的割り当て処理を軽減することが出来ます。

2.ArrayListのコンストラクタに引数を指定しない場合は10個の要素を持った配列が作られます。

/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this(10);
}
ArrayList.java 1.56 06/04/21