なぜベクトル配列が2倍になるのですか？

Question

Vector（Java向けのArrayList）の従来の実装が、3倍または4倍ではなく、各拡張で内部配列サイズを2倍にするのはなぜですか？

Answer 1

ベクターに挿入する平均時間を計算するときは、成長しない挿入と成長する挿入を考慮する必要があります。

オペレーションの総数を呼び出して、 n 個のアイテム o _total を挿入し、平均 o _average 。

n 個のアイテムを挿入し、必要に応じて A 倍に拡大すると、 o _total = n + <！>＃931; A ⁱ [0 <！> lt; i <！> lt; 1 + ln _A n] 操作。最悪の場合、割り当てられたストレージの 1 / A を使用します。

直感的に、 A = 2 は最悪の場合 o _total = 2n を意味するため、 o _average はO（1）であり、最悪の場合は割り当てられたストレージの50％を使用します。

より大きな A の場合、 o _total は低くなりますが、無駄なストレージが増えます。

小さい A の場合、 o _total は大きくなりますが、それほど多くのストレージを無駄にしません。幾何学的に大きくなる限り、挿入時間はまだO（1）ですが、定数は高くなります。

成長因子1.25（赤）、1.5（シアン）、2（黒）、3（青）、および4（緑）の場合、これらのグラフはポイントおよび平均サイズ効率（サイズ/割り当てられたスペースの比率、より多い方が良い） ）左側にあり、400,000個のアイテムを挿入するための時間効率（挿入/操作の比率。多いほど良い）。サイズ変更の直前に、すべての成長因子について100％のスペース効率が達成されます。 A = 2 の場合、時間効率は25％から50％の間であり、スペース効率は約50％であり、ほとんどの場合に適しています：

Javaなどのランタイムの場合、配列はゼロで埋められるため、割り当てる操作の数は配列のサイズに比例します。これを考慮すると、時間効率の推定値の差が小さくなります。

Answer 2

配列（または文字列）のサイズを指数関数的に2倍にすることは、配列内に十分なセルを配置することと、メモリを大量に浪費することの間の適切な妥協です。

10個の要素から始めましょう：

1-10
2-20
3-40
4-80
5-160

サイズを3倍にすると、成長が速すぎます

1-10
2-30
3-90
4-270
5-810

実際には、10倍または12倍に成長します。トリプルの場合は、7回または8回実行します。再割り当ての実行時ヒットは、この数回は心配するのに十分小さいですが、必要なサイズを完全にオーバーシュートする可能性が高くなります。

Answer 3

メモリの異常なサイズのブロックを割り当てる場合、そのブロックの割り当てが解除されると（サイズを変更するか、GCされるため）、メモリに異常なサイズの穴ができ、メモリマネージャーの頭痛。したがって、通常は2の累乗でメモリを割り当てることをお勧めします。場合によっては、基礎となるメモリマネージャーは特定のサイズのブロックのみを提供し、奇妙なサイズを要求すると、次の大きなサイズに切り上げられます。 470ユニットを要求し、とにかく512を取得し、要求した470をすべて使用した後にサイズを変更するのではなく、512を最初から要求することもできます。

Answer 4

すべての倍数は妥協です。大きくしすぎると、メモリを無駄に使いすぎます。小さすぎると、再割り当てとコピーに多くの時間を無駄にします。倍増は機能し、実装が非常に簡単であるためだと思います。また、1.5を乗数として使用する独自のSTLライクなライブラリを見ました-その開発者は、メモリを2倍に浪費することを検討したと思います。

Answer 5

Vector および ArrayList 、それは必ずしも各拡張で倍になりません。

VectorのJavadocから：

  

各ベクトルは、capacityとcapacityIncrementを維持することにより、ストレージ管理を最適化しようとします。容量は常に少なくともベクトルサイズと同じ大きさです。コンポーネントがベクターに追加されると、ベクターのストレージがensureCapacity(int minCapacity)のサイズでチャンク単位で増加するため、通常は大きくなります。アプリケーションは、多数のコンポーネントを挿入する前にベクターの容量を増やすことができます。これにより、増分再割り当ての量が削減されます。

ベクターのコンストラクターの1つでは、ベクターの初期サイズと容量の増分を指定できます。 Vectorクラスには、ベクターの最小サイズを手動で調整し、ベクターのサイズを自分で変更するためのsetSize(int newSize)およびArrayListも用意されています。

ArrayListクラスは非常に似ています：

  

各<=>インスタンスには容量があります。容量は、リスト内の要素を格納するために使用される配列のサイズです。常に少なくともリストのサイズと同じ大きさです。 ArrayListに要素が追加されると、その容量は自動的に増加します。成長ポリシーの詳細は、要素を追加すると一定の償却時間コストがかかるという事実以外には指定されません。

     

アプリケーションは、ensureCapacity操作を使用して多数の要素を追加する前に、<=>インスタンスの容量を増やすことができます。これにより、増分再割り当ての量を減らすことができます。

ベクトルの一般的な実装について尋ねる場合は、サイズの増加の選択よりも、トレードオフがどの程度かを選択します。一般的に、ベクトルは配列によって支えられています。配列は固定サイズです。ベクトルがいっぱいであるためにベクトルのサイズを変更するということは、配列のすべての要素を新しい大きな配列にコピーする必要があることを意味します。新しい配列を大きくしすぎると、決して使用しないメモリが割り当てられます。小さすぎる場合、要素を古い配列から新しい大きな配列にコピーするのに時間がかかりすぎる可能性があります。これはあまり頻繁に実行したくない操作です。

Answer 6

個人的には、それは意的な選択だと思います。基数2の代わりに基数eを使用できます（複数のサイズを（1 + e）で2倍する代わりに）。

ベクトルに大量の変数を追加する場合は、ベースを大きくすると有利です（実行するコピーの量を減らすため）。 avgで少数のメンバーのみを使用する場合は、ベースが低いほうが適切であり、オーバーヘッドの量が減るため、速度が向上します。

ベース2は妥協です。

Answer 7

すべてが同じ大きなOパフォーマンスプロファイルを持っているため、2倍と3倍または4倍のパフォーマンスの理由はありません。ただし、絶対的な意味では、通常のシナリオでは2倍にするとスペース効率が向上する傾向があります。