157

の通常のコンストラクタArrayListは次のとおりです。

ArrayList<?> list = new ArrayList<>();

ただし、初期容量のパラメーターを持つオーバーロードされたコンストラクターもあります。

ArrayList<?> list = new ArrayList<>(20);

ArrayList好きなように追加できるのに、初期容量でを作成すると便利なのはなぜですか？

4

11 に答える 11

204

のサイズが事前にわかっている場合ArrayListは、初期容量を指定する方が効率的です。これを行わないと、リストが大きくなるにつれて、内部配列を繰り返し再割り当てする必要があります。

最終リストが大きいほど、再割り当てを回避することで時間を節約できます。

とはいえ、事前に割り当てなくてもn、の後ろに要素を挿入するArrayListと、合計O(n)時間がかかることが保証されます。つまり、要素の追加は、償却された定数時間演算です。これは、各再割り当てで配列のサイズを指数関数的に、通常は係数で増加させることによって実現され1.5ます。このアプローチでは、操作の総数をで示すことができますO(n)。

于 2013-03-15T10:41:57.250 に答える
41

ArrayListは動的にサイズ変更される配列データ構造であるため、初期（デフォルト）の固定サイズの配列として実装されます。これがいっぱいになると、配列は2倍のサイズに拡張されます。この操作にはコストがかかるため、できるだけ少なくする必要があります。

したがって、上限が20アイテムであることがわかっている場合は、初期長が20の配列を作成する方が、デフォルトの15などを使用してから、サイズを変更して15*2 = 3020のみを使用し、拡張のサイクルを無駄にするよりも優れています。

PS-AmitGが言うように、拡張係数は実装固有です（この場合(oldCapacity * 3)/2 + 1）

于 2013-03-15T10:47:03.330 に答える
25

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を作成する方がよいでしょう。

于 2013-03-15T10:44:05.860 に答える
17

私は実際に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サイズコンストラクタなしで作成すると、通常はO（1）またはサイズ変更時にO（n）ArrayList.add 1000000かかる時間が呼び出されます。

1000000 + 16 + 25 + ... + 670205 + 1005308= 4015851操作

コンストラクターを使用してこれを比較してから、 O（1）ArrayList.addで実行されることが保証されている呼び出しを行います。

1000000 + 1000000= 2000000操作

JavaとC＃

Javaは上記のとおりであり、で開始し10、各サイズ変更をで増やしていきます50% + 1。C＃はで始まり、4はるかに積極的に増加し、サイズ変更ごとに2倍になります。上記のC＃の1000000addsの例では、3097084操作を使用しています。

参考文献

于 2013-03-16T05:44:04.843 に答える
10

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に追加されると、その容量は自動的に増加します。成長政策の詳細は、要素を追加することで一定の償却時間コストがかかるという事実を超えて特定されていません。」

もちろん、どのような範囲を保持するかわからない場合は、サイズを設定することはおそらく良い考えではありませんが、特定の範囲を念頭に置いている場合は、初期容量を設定するとメモリ効率が向上します。

于 2013-03-15T10:42:43.160 に答える
3

ArrayListには多くの値を含めることができ、大きな初期挿入を行う場合、次のアイテムにより多くのスペースを割り当てようとするときにCPUサイクルを無駄にしないように、最初に大きなストレージを割り当てるようにArrayListに指示できます。したがって、最初にスペースを割り当てる方が効率的です。

于 2013-03-15T10:45:51.457 に答える
3

これは、すべてのオブジェクトの再割り当てにかかる可能性のある作業を回避するためです。

int newCapacity = (oldCapacity * 3)/2 + 1;

内部的new Object[]に作成されます。配列リストに要素を追加するとき、
JVMは作成するための努力が必要 です。new Object[]再割り当てのための上記のコード（あなたが考える任意のアルゴリズム）がない場合は、呼び出すたびarraylist.add()にnew Object[]作成する必要がありますが、これは無意味であり、追加するオブジェクトごとにサイズを1ずつ増やすための時間が失われています。Object[]したがって、次の式でサイズを大きくすることをお勧めします。
（JSLは、毎回1ずつ増加するのではなく、動的に増加するarraylistに以下に示す予測式を使用しました。拡張するには、JVMによる労力が必要です）

int newCapacity = (oldCapacity * 3)/2 + 1;
于 2013-03-15T12:09:46.930 に答える
2

各ArrayListは、初期容量値「10」で作成されていると思います。したがって、とにかく、コンストラクター内で容量を設定せずにArrayListを作成すると、デフォルト値で作成されます。

于 2013-03-15T10:44:14.300 に答える
2

最適化だと思います。初期容量のないArrayListには、最大10の空の行があり、追加を行うと拡張されます。

正確な数のアイテムのリストを作成するには、trimToSize（）を呼び出す必要があります

于 2013-03-15T10:46:23.040 に答える
0

での私の経験によるとArrayList、初期容量を与えることは、再割り当てコストを回避するための良い方法です。ただし、注意が必要です。上記のすべての提案は、要素数の概算がわかっている場合にのみ初期容量を提供する必要があると述べています。ただし、何も考えずに初期容量を指定しようとすると、リストが必要な数の要素に満たされると必要になることはないため、予約および未使用のメモリの量は無駄になります。私が言っているのは、容量を割り当てながら最初は実用的であり、実行時に必要な最小容量を知るための賢い方法を見つけることができるということです。ArrayListは、と呼ばれるメソッドを提供しますensureCapacity(int minCapacity)。しかし、その後、賢い方法を見つけました...

于 2013-04-13T07:31:39.347 に答える
0

initialCapacityを使用した場合と使用しない場合でArrayListをテストしましたが、驚くべき結果が得
られました。LOOP_NUMBERを100,000以下に設定すると、initialCapacityの設定が効率的になります。 

list1Sttop-list1Start = 14
list2Sttop-list2Start = 10


しかし、LOOP_NUMBERを1,000,000に設定すると、結果は次のように変わります。 

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でテストしました

于 2016-06-04T13:56:17.973 に答える