はじめに
Javaでリストを作成するとき、以下のようにnew ArrayList<>()と書いてインスタンスを作成する例をよく目にするかと思います。
List<String> list = new ArrayList<>();
しかし、以下のようにnew ArrayList<>()の()内に数値を記述してインスタンスを作成することもできます。
List<String> list = new ArrayList<>(500);
上記例の500にあたる部分が、initialCapacityと呼ばれる引数です。このinitialCapacityを利用することで、リストの操作のパフォーマンスを向上させることができます。
この記事では、initialCapacityに関する情報と、その使い方について解説します。
まとめ
記事が少し長くなってしまったので、先に結論を記載します。詳細については以降で説明していきます。
-
initialCapacityとは
- ArrayListインスタンスは、内部的には配列を利用したデータです。
- initialCapacityを指定することで、指定した値と同じサイズの配列を内部に持つArrayListインスタンスを生成できます。
-
ArrayListのパフォーマンスを良くする方法
- 格納される要素数が10,000～50,000のように、ある程度要素数の範囲を予測できるのであればinitialCapacityを指定しましょう。これにより、要素を追加する際のオーバーヘッドを回避できます。
- initialCapacityを指定しても、
size()メソッドのような要素数の取得処理には影響ありません。 - initialCapacityにどんな数値を指定するかは、何を優先するかで決まります。例えば格納される要素数が10,000～50,000の場合、最大値の50,000を指定すれば、多くのメモリを無駄にする可能性がある一方、オーバーヘッドは発生しなくなります。
-
trimToSize()メソッドを使用してサイズを切り詰めることができますが、オーバーヘッドが発生するため、必ずしも実行するべきとは限りません。
initialCapacityとは
initialCapacityがどのように使われているのか、ArrayListの内部処理を見て確認しましょう。initialCapacityを指定する場合のコンストラクタの内部は以下の通りです。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
// ...省略...
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
// ...省略...
}
initialCapacityが1以上の値の場合、その値のサイズ（要素数）を持つ配列を生成しています。そして生成した配列を、メンバー変数elementDataに代入しています。initialCapacityが0の場合には、空の配列がelementDataに代入されます。
リストに対して要素を追加したり、要素を取得したりするとき、このelementDataに要素の追加／取得が行われます。つまりArrayListは、内部的には配列を利用したデータ構造です。
つまり new ArrayList<>(500)と書いた場合、サイズが500の配列を持つArrayListインスタンスが生成されます。
次に、initialCapacityを指定しない場合のArrayListのコンストラクタの処理を見ていきましょう。内部処理は以下の通りです。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// ...省略...
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// ...省略...
}
initialCapacityが0の場合と同じく、空の配列をelementDataに代入しています。
つまり new ArrayList<>()と書いた場合、要素数が0の配列を持つArrayListインスタンスが生成されます。
なお、initialCapacityを指定した際、要素数の取得処理（size()メソッド呼び出し）に影響が出ないか不安に思うかもしれませんが、こちらは問題ありません。size()メソッドやisEmpty()メソッドは単に配列のサイズを返すのではなく、メンバー変数sizeを値を用いて結果を返すようになっています。このsize変数は要素の操作が行われた際に増減するようになっており、ArrayListの内部ではこの変数の値で要素数を管理しています。
※要素数に関するArrayListの内部処理（長いので折りたたんでいます）
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
// ...省略...
/**
* This helper method split out from add(E) to keep method
* bytecode size under 35 (the -XX:MaxInlineSize default value),
* which helps when add(E) is called in a C1-compiled loop.
*/
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
/**
* Returns the number of elements in this list.
*
* @return the number of elements in this list
*/
public int size() {
return size;
}
// ...省略...
}
publicのadd(e)メソッドが実行された際、privateのaddメソッド内で変数sizeの値を増加させていることが分かると思います。
そのため、initialCapacityを500と指定して、実際に格納された要素数が200だった場合でも、size()メソッドは正しい要素数200を返します。
要素が追加された時のArrayListの挙動
new ArrayList<>()で生成したArrayListが持っているのは空の配列ですが、複数回要素を追加しても例外は発生しません。
ArrayListの内部では「要素が追加された時、空き容量が不足していた場合により大きいサイズの配列を新しく作成し、そこに旧配列の要素データをコピーする」という処理を行うためです。
具体的には、new ArrayList<>()で生成したArrayListに対してadd(e)を行った場合、ArrayListの内部ではサイズが10の配列が生成されます。さらにadd(e)を10回行った場合、サイズが15の配列が生成されます。（最大要素数を超えるたびにサイズが1.5倍の配列が生成されていきます）
このようにArrayListは配列のサイズが自動的に拡張する仕組みを有しています。
※要素コピーに関するArrayListの内部処理（長いので折りたたんでいます）
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
* @throws OutOfMemoryError if minCapacity is less than zero
*/
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
private Object[] grow() {
return grow(size + 1);
}
/**
* This helper method split out from add(E) to keep method
* bytecode size under 35 (the -XX:MaxInlineSize default value),
* which helps when add(E) is called in a C1-compiled loop.
*/
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
// ...省略...
}
※他のjavaのバージョンの場合、内部処理は異なりますが、grow()メソッド内でArrays.copyOf()を行っている点は共通です。
grow()メソッド内で、「大きいサイズの配列を新しく作成し、旧配列の要素データをコピーする」という処理を行っていることが分かると思います。
要素が追加された時のArrayListのパフォーマンス
問題は、何度も要素の追加を行った際に、メモリ再割り当てのオーバーヘッドが発生することです。 リストのサイズに比例してそのコストは増加します。
例えばnew ArrayList<>()で生成したArrayListに対してadd(e)を500回行った場合、ArrayListの内部の配列のサイズは10, 15, 22, 33, 49...と増加していき、最終的にサイズが549の配列が生成されます。それまでに配列の拡張処理（オーバーヘッド）が11回行われます。その処理分だけ処理速度も落ちます。一方、new ArrayList<>(500)としておけば、最初にサイズが500の配列が生成されるため、配列の拡張処理は実行されずに済みます。
initialCapacityを指定する場合と指定しない場合の実行速度を比較してみましょう。以下の例では5,000,000回add(e)を行った際の実行結果です。
initialCapacityを指定しない場合：258ms
long startTime = System.currentTimeMillis();
List<String> defaultList = new ArrayList<>();
for (int i = 0; i < 5_000_000; i++) {
defaultList.add("str");
}
long endTime = System.currentTimeMillis();
System.out.println("time: " + (endTime1 - startTime1) + "ms"); // time: 258ms
initialCapacity: 5,000,000 を指定した場合：144ms
long startTime = System.currentTimeMillis();
List<String> listSpecifiedCapacity = new ArrayList<>(5_000_000);
for (int i = 0; i < 5_000_000; i++) {
listSpecifiedCapacity.add("str");
}
long endTime = System.currentTimeMillis();
System.out.println("time: " + (endTime - startTime) + "ms"); // time: 144ms
私の環境では上記結果となりました。
initialCapacityを指定した方が、オーバーヘッドが発生しないため、実行速度が速いことが分かります。
ArrayListのパフォーマンスを良くする方法
格納すべき要素数が想定できるのであれば、initialCapacityを指定することをお勧めします。 これにより、要素を追加する際のオーバーヘッドを回避できます。
前述の例の通り、new ArrayList<>()で生成したArrayListに対してadd(e)を500回行った場合、ArrayListの内部では配列の拡張処理（オーバーヘッド）が11回行われますが、new ArrayList<>(500)としておけば、add(e)を500回行った場合でも配列の拡張処理は実行されずに済みます。その分だけ実行速度も高速になります。
また、そちらの方がメモリの無駄使いも発生しません。new ArrayList<>()で生成したArrayListに対してadd(e)を500回行った場合、最終的にサイズが549の配列が生成されますが、格納されている要素数は500で、残り49は使用されていません。
前述の例のように、はっきりと要素数が想定できるケースは少ないと思います。そういった場合でも一定の範囲内の要素数が予測できるのであれば、initialCapacityを指定した方が良いでしょう。
例えば要素数が10,000～50,000になることが分かっているのであれば、initialCapacityは10,000としても良いでしょう。new ArrayList<>()とするより、new ArrayList<>(10000)とした方が、配列が10,000を超えるまでの間に拡張処理が行われずに済むため、オーバーヘッドが少なくなります。
もしくはinitialCapacityを50,000としても良いでしょう。格納された要素数が21,000だった場合、29,000の空きが発生してしまいますが、配列の拡張処理が行われないためオーバーヘッドが発生しないというメリットがあります。
ArrayListには、内部の配列（elementData）のサイズを、実際に格納されている要素数にトリミングするtrimToSize()メソッドがありますが、一概にtrimToSize()メソッドを使う方が良いとは言えません。
前述の例では29,000の空きが発生しているため、trimToSize()メソッドを呼び出して、配列のサイズを21,000まで切り詰めた方が良いように思えます。確かにメモリの無駄使いという面で考えればtrimToSize()メソッドを呼び出した方が良いです。ただtrimToSize()メソッドの内部では「配列を新しく作成し、旧配列の要素データをコピーする」という処理を行っているため、オーバーヘッドが発生します。処理速度を優先したい場合、trimToSize()メソッドは呼び出さない方が良いことになります。
さらに、trimToSize()メソッド呼び出し後に要素の追加操作を行うとパフォーマンスに影響が出るというデメリットもあります。trimToSize()メソッドを呼び出すと、配列のサイズが現在の要素数になることから、trimToSize()メソッド実行後に要素の追加を行うとオーバーヘッドが発生します。この問題を避けるためには、trimToSize()メソッド呼び出し後に要素を追加しなければ良いのですが、例えば実装後の機能改修の内容によっては難しい場面も出てくるかと思います。trimToSize()メソッド実行後に要素を追加する処理が実装される可能性がある場合、安易にtrimToSize()メソッドを呼び出すべきではありません。
おわりに
まとめ は記事上部に記載しています。
ArrayListのinitialCapacityに関する情報を調べても、詳細が書かれたサイトがあまり見つからなかったので今回執筆しました。
記事執筆にあたり色々調べてみましたが、initialCapacityはもっと周知されても良いのではと感じました。まとめにも記載しましたが、格納される要素数の範囲がある程度予測できる場合にはinitialCapacityを利用するメリットがあります。こういったケースで適切に使えば、さほどデメリットなくパフォーマンスの良い処理が実装できるかと思います。
参考
-
【Java】ArrayListのcapacityの増え方
- ArrayListの内部処理を理解するために活用させていただきました。