ArrayList`の通常のコンストラクタは以下の通りである:
ArrayList<?> list = new ArrayList<>();
しかし、オーバーロードされたコンストラクタもある:
ArrayList<?> list = new ArrayList<>(20);
好きなように追加できるのに、なぜ初期容量を持つArrayList
を作るのが便利なのだろうか?
あらかじめ ArrayList
のサイズがわかっている場合は、初期容量を指定した方が効率的である。そうしないと、リストが大きくなるにつれて内部配列を繰り返し再割り当てしなければならなくなる。
最終的なリストが大きければ大きいほど、再割り当てを避けることで時間を節約できる。
とはいえ、事前アロケーションを行わない場合でも、 ArrayList
の後ろに n
個の要素を挿入するには、合計で O(n)
の時間がかかることが保証されている。言い換えると、要素の追加は償却された定数時間操作である。これは、再割り当てのたびに配列のサイズを指数関数的に、通常は 1.5
倍に増加させることで実現される。このアプローチでは、操作の総数は O(n)
であることを示すことができる。
ArrayList
は動的サイズ変更配列データ構造であるため、初期(デフォルト)固定サイズの配列として実装されます。 これがいっぱいになると、配列はダブルサイズの配列に拡張されます。 この操作にはコストがかかるため、できるだけ少なくする必要があります。
したがって、上限が20アイテムであることがわかっている場合は、初期長が20のアレイを作成することは、デフォルト、たとえば15を使用してそれを「15 * 2 = 30」にサイズ変更し、無駄にして20だけを使用するよりも優れています。拡張のためのサイクル。
追伸-AmitGが言うように、拡張係数は実装固有です(この場合、 (oldCapacity * 3)/ 2 + 1
)。
Arraylistのデフォルトのサイズは10である。
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this(10);
}
そのため、100以上のレコードを追加しようとすると、メモリの再割り当てによるオーバーヘッドが発生する。
ArrayList<?> list = new ArrayList<>();
// same as new ArrayList<>(10);
ですから、もしArraylistに格納する要素の数が決まっているのであれば、10で始めてどんどん増やしていくのではなく、そのサイズでArraylistを作成した方がよいでしょう。
2か月前にこのトピックについてブログ投稿を実際に書きました。 この記事はC#の「List< T>」用ですが、Javaの「ArrayList」は非常によく似た実装をしています。 ArrayList
は動的配列を使用して実装されるため、オンデマンドでサイズが大きくなります。 したがって、容量コンストラクターの理由は、最適化の目的です。
これらのサイズ変更操作の1つが発生すると、ArrayListは配列の内容を古い配列の2倍の容量である新しい配列にコピーします。 この操作は O(n)時間で実行されます。
例。 -------。
ArrayList
のサイズがどのように増加するかについての例を次に示します。
10
16
25
38
58
... 17 resizes ...
198578
297868
446803
670205
1005308
したがって、リストは「10」の容量で始まり、11番目のアイテムが追加されると、「50%+ 1」増加して「16」になります。 17番目のアイテムでは、「ArrayList」が再び「25」に増加します。 次に、目的の容量がすでに「1000000」として知られているリストを作成している例を検討します。 サイズコンストラクターなしで「ArrayList」を作成すると、「ArrayList.ad d」の「1000000」回が呼び出され、通常 O(1)またはサイズ変更時に O(n)かかります。
1000000 + 16 + 25 +。 ... + 670205 + 1005308 = 4015851操作。
コンストラクターを使用してこれを比較し、 O(1)で実行することが保証されている ArrayList.ad d
を呼び出します。
1000000 + 1000000 = 2000000操作。
Java対C#。 ----------。
Javaは上記のように、「10」から始まり、各サイズを「50%+ 1」に増やします。 C#は 4
から始まり、はるかに積極的に増加し、サイズごとに2倍になります。 1000000
は、C#の上からの例を追加し、 3097084
操作を使用します。
参照。 ----------。
ArrayListの初期サイズ、例えばArrayList<>(100)
を設定することで、内部メモリの再割り当ての回数を減らすことができる。
**例
ArrayList example = new ArrayList<Integer>(3);
example.add(1); // size() == 1
example.add(2); // size() == 2,
example.add(2); // size() == 3, example has been 'filled'
example.add(3); // size() == 4, example has been 'expanded' so that the fourth element can be added.
上の例でわかるように、ArrayList
は必要に応じて拡張することができる。これではわからないのは、ArrayListのサイズは通常2倍になるということです(ただし、新しいサイズは実装に依存することに注意してください)。以下はOracleからの引用です:
各ArrayListインスタンスには容量があります。容量は のサイズです。これは常に 少なくともリストサイズと同じ大きさです。要素が ArrayListに要素が追加されると、その容量は自動的に大きくなります。増加の詳細 gt;ポリシーの詳細は、要素を追加する際に 一定の償却時間コストがかかる;
もちろん、どのような範囲を保持するのか見当がつかない場合、サイズを設定することはおそらく良い考えではないでしょう - しかし、特定の範囲を念頭に置いている場合、初期容量を設定することでメモリ効率が向上します。
これは、すべてのオブジェクトの再割り当てのための可能な努力を回避するためです。
int newCapacity = (oldCapacity * 3)/2 + 1;
内部で「新しいオブジェクト[]」が作成されます。
配列リストに要素を追加する場合、JVMは「新しいオブジェクト[]」を作成する作業が必要です。 再割り当てのための上記のコード(あなたが考えるすべてのアルゴ)がない場合、 arraylist.ad d()
を呼び出すたびに、 new Object []
を作成する必要があります。これは無意味であり、時間を失っています。追加するすべてのオブジェクトのサイズを1ずつ増やします。 したがって、次の式で「オブジェクト[]」のサイズを大きくすることをお勧めします。
。
(JSLは、動的に成長するアレイリストに対して、毎回1ずつ成長するのではなく、以下に示すフォーキャスト式を使用しています。 成長するにはJVMによる努力が必要だからです)。
int newCapacity = (oldCapacity * 3)/2 + 1;
ArrayList
での私の経験によれば、初期容量を与えることは、再割り当てコストを回避するための良い方法です。 しかし、それは警告を出します。 上記のすべての提案は、要素の数の大まかな推定がわかっている場合にのみ初期容量を提供する必要があると述べています。 ただし、何も考えずに初期容量を提供しようとすると、リストが必要な数の要素に満たされると必要になることがないため、予約済みで未使用のメモリの量は無駄になります。 私が言っていることは、容量を割り当てる間、最初は実用的であり、実行時に必要な最小容量を知る賢い方法を見つけることができるということです。 ArrayListは、「ensureCapacity(int minCapacity)」と呼ばれるメソッドを提供します。 しかし、その後、賢い方法を見つけました。..
arrayListをinaryCapacityの有無にかかわらずテストしましたが、驚くべき結果が得られました。
< br />。 LOOP_NUMBERを100,000以下に設定すると、initaryCapacityの設定が効率的になります。list1Sttop-list1Start = 14
list2Sttop-list2Start = 10
list1Stop-list1Start = 40
list2Stop-list2Start = 66
public static final int LOOP_NUMBER = 100000;
public static void main(String[] args) {
long list1Start = System.currentTimeMillis();
List<Integer> list1 = new ArrayList();
for (int i = 0; i < LOOP_NUMBER; i++) {
list1.add(i);
}
long list1Stop = System.currentTimeMillis();
System.out.println("list1Stop-list1Start = " + String.valueOf(list1Stop - list1Start));
long list2Start = System.currentTimeMillis();
List<Integer> list2 = new ArrayList(LOOP_NUMBER);
for (int i = 0; i < LOOP_NUMBER; i++) {
list2.add(i);
}
long list2Stop = System.currentTimeMillis();
System.out.println("list2Stop-list2Start = " + String.valueOf(list2Stop - list2Start));
}
windows8.1とjdk1.7.0_80でテストしました。