11

プリミティブであろうとなかろうと、配列のサイズを動的に変更できない理由は何ですか?

を使用できることはわかっていますがArrayList、その背後にある実装はまだ初期サイズの配列 (デフォルトでは 50 だと思います) であり、50 を超えると、それらの要素を含む新しい配列が作成されます。

そのため、サイズを変更できない配列のシステム仕様を理解しようとしています。

4

4 に答える 4

4

配列は、ボンネットの下では、連続したメモリ ブロックです。何を初期化するかに応じて、比較的小さくすることも、比較的大きくすることもできます。

たとえば、10 個の要素の配列があるとします。

int[] arr = new int[10];

JVM の基盤となる実装は、プログラムに割り当てられる連続する 40 バイトを OS に要求する必要があります。OS の義務により、おなじみの名前で使用できる 40 バイトが得られましたarr。

この配列は、その両側でスペースを共有している可能性が高いことに注意してください。近くに他の参照または情報のビットがあり、それ自体の 11 番目の位置まで歩いて「要求」することはできません。

10 は短すぎると判断したとしましょう。10 倍大きくする必要があります。

int arr2 = new int[100];

現在、OS はメモリ内で互いに隣接する 400 バイトのスペースを見つける必要があります。これは、オブジェクトのライフサイクルやガベージ コレクションの実行時間などを考えると、些細なことかもしれません。

配列のサイズ変更は、参照をいくつかのメモリの場所に移動するだけではありません。連続したメモリの新しいブロックを見つけてデータを格納することです。

あなたが言及ArrayListしたのは、「自動的に」サイズ変更を行う配列に支えられているという点で興味深いことです。サイズ変更操作には問題があります。費用がかかります。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

それensureCapacityInternalはいくつかの興味深いことを行います...最終的に呼び出します...最終ensureExplicitCapacity的に呼び出しますgrow：

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

基本的に、サイズ変更が必要になるたびに、元のバッキング配列の 1.5 倍に相当するスペースが割り当てられます。がかなり大きい場合、これは非常に急速にコストArrayListがかかります。システムは外に出て、割り当てるためにますます多くの連続したメモリを見つける必要があります。つまり、JVM は連続したスペースをさらに見つける必要があります。つまり、ガベージ コレクションに費やす時間が長くなり、最終的には少ない意味になります。パフォーマンス。

そして、上記はデータをコピーして戻すことさえカバーしていません。

于 2013-11-05T06:00:45.833 に答える