『VectorとArrayList』

Javaには、オブジェクトの可変長配列を実装する
java.util.Vectorとjava.util.ArrayListというクラスが提供されていますが、
内部的にはelementDataという
Object型の配列に要素を格納していっています。
利用する側は、何も考えずにaddメソッド(要素の追加・挿入を行う)を
使えば勝手に要素が追加されていっているような感じがしますが、
Vector・ArrayListの内部では要素追加時に現在のelementDataのサイズを
拡大する処理を行っています。

VectorとArrayListを、デフォルトコンストラクタでインスタンスを生成した場合、
それぞれのelementDataはサイズ10で初期化されます。


Vector vec = new Vector(); ・・・・1
ArrayList arr = new ArrayList(); ・・・・2

String value = "value";

for (int i = 0; i < 11; i++) {
vec.add(value); ・・・・3
arr.add(value); ・・・・4
}

※ 1、 2 の段階では、それぞれのelementDataはサイズが10です。
※ for文において、i == 10 の時の、3・4のコード実行時にelementDataの
容量拡大の処理がそれぞれ行われます。



Vectorの容量拡大の処理は、現在のelementDataのサイズを
2倍した数でelementDataを生成しなおしています。
上記例でいいますと、i == 10 の時の、addメソッド実行時に
vecのelementDataはサイズ20になります。

ArrayListの容量拡大の処理は、現在のelementDataのサイズを
3倍した数を2で割って、更にその後 + 1を足した数で
elementDataを生成しなおしています。
※(elementDataのサイズ * 3) / 2 + 1 になります。
上記例でいいますと、i == 10 の時の、addメソッド実行時にarrの
elementDataはサイズ16になります。

以上を踏まえた上で、下記コードをみてみます。


// VectorTime.java
import java.util.Vector;

public class VectorTime {
public static void main(String[] args) {
String string = "ArrayValue";
for (int i = 0; i < 10; i++) {
Vector vector = new Vector();
long time = System.currentTimeMillis();
for (int j = 0; j < 5000000; j++) {
vector.add(string);
}
System.out.println("Time = " + (System.currentTimeMillis() - time));
}
}
}

// VectorTime.javaの実行結果
Time = 951
Time = 701
Time = 1112
Time = 951
Time = 1092
Time = 1131
Time = 1202
Time = 1082
Time = 1051
Time = 861


// ArrayListTime.java
import java.util.ArrayList;

public class ArrayListTime {
public static void main(String[] args) {
String string = "ArrayValue";
for (int i = 0; i < 10; i++) {
ArrayList arrayList = new ArrayList();
long time = System.currentTimeMillis();
for (int j = 0; j < 5000000; j++) {
arrayList.add(string);
}
System.out.println("Time = " + (System.currentTimeMillis() - time));
}
}
}

// ArrayListTime.javaの実行結果
Time = 1362
Time = 1212
Time = 1081
Time = 1082
Time = 1062
Time = 1091
Time = 1072
Time = 1071
Time = 1072
Time = 1111


上記のVectorTime.javaとArrayListTime.javaは、addメソッドを
5000000回実行した時にかかる時間を測定するプログラムですが、
Vectorのメソッドはsynchronizedされているので処理が重くなりますが、
上記のプログラムではArrayListよりVectorの方が
処理に要する時間は短くなっています。なぜか？
理由は要素追加時の容量拡大処理回数にあります。
上記のVectorTime.javaとArrayListTime.javaでは、
それぞれ容量拡大の処理回数が異なります。
addメソッドを5000000回実行する際、VectorTime.javaでは22回、
ArrayListTime.javaでは35回、容量拡大の処理が行われています。
ArrayListTime.javaの方が13回多く容量拡大の処理を行っています。
その為、処理時間がVectorTime.javaより多くなっています。
では、本当に容量拡大の処理回数が原因なのか？
そこで下記のプログラムを見てみます。


// VectorTime2.java
import java.util.Vector;

public class VectorTime2 {
public static void main(String[] args) {
String string = "ArrayValue";
for (int i = 0; i < 10; i++) {
// 容量を初めから5000000でインスタンスを生成
Vector vector = new Vector(5000000);
long time = System.currentTimeMillis();
for (int j = 0; j < 5000000; j++) {
vector.add(string);
}
System.out.println("Time = " + (System.currentTimeMillis() - time));
}
}
}


// ArrayListTime2.java
import java.util.ArrayList;

public class ArrayListTime2 {
public static void main(String[] args) {
String string = "ArrayValue";
for (int i = 0; i < 10; i++) {
// 容量を初めから5000000でインスタンスを生成
ArrayList arrayList = new ArrayList(5000000);
long time = System.currentTimeMillis();
for (int j = 0; j < 5000000; j++) {
arrayList.add(string);
}
System.out.println("Time = " + (System.currentTimeMillis() - time));
}
}
}

上記のVectorTime2.javaとArrayListTime2.javaは、
VectorTime.java、ArrayListTime.javaと殆ど同じプログラムですが、
一箇所だけ違います。VectorとArrayListのインスタンスを生成する際、
初めから容量を5000000でインスタンスの生成をしています。
これでaddメソッドを5000000回実行しても、
容量拡大の処理は一回たりとも行われない事になります。
では実行結果を見てみます。

// VectorTime2.javaの実行結果 // ArrayListTime2.javaの実行結果
Time = 441 Time = 270
Time = 471 Time = 281
Time = 430 Time = 270
Time = 471 Time = 281
Time = 481 Time = 270
Time = 471 Time = 270
Time = 471 Time = 271
Time = 471 Time = 270
Time = 470 Time = 271
Time = 470 Time = 280

今度は、ArrayListTime2.javaの処理時間の方が少なくなりました。

インスタンスに大量の拡大領域を事後アロケートするのが明白な場合には
アロケートのオーバーヘッドをできる限り避けるために、最低限のcapacityを
事前確保するように心がけましょう。