Vector (Java の場合は ArrayList) の従来の実装が、拡張ごとに内部配列サイズを 3 倍または 4 倍にするのではなく、2 倍にするのはなぜですか?
5811 次
7 に答える
21
ベクターに挿入する平均時間を計算するときは、成長していない挿入と成長している挿入を考慮する必要があります。
n 個のアイテムを挿入する操作の総数をo total、平均をo averageと呼びます。
n 個のアイテムを挿入し、必要に応じてA倍に拡大すると、o total = n + ΣA i [ 0 < i < 1 + ln A n ]操作が行われます。最悪の場合、割り当てられたストレージの1/Aを使用します。
直観的に、A = 2は、最悪でもo total = 2nを意味するため、o平均は 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 などのランタイムの場合、配列はゼロで埋められるため、割り当てる操作の数は配列のサイズに比例します。これを考慮すると、時間効率の推定値の差が小さくなります。
于 2009-09-15T09:12:20.650 に答える
5
任意の倍数は妥協です。大きくしすぎると、メモリを浪費しすぎます。小さすぎると、再割り当てとコピーに多くの時間を浪費します。二重化は機能し、実装が非常に簡単であるため、そこにあると思います。また、1.5 を乗数として使用する専用の STL ライクなライブラリも見ました。その開発者は、2 倍にするとメモリを浪費しすぎると考えたようです。
于 2009-09-15T05:58:39.107 に答える
4
配列 (または文字列) のサイズを指数関数的に 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 倍に成長します。3 倍にする場合は、おそらく 7 回または 8 回実行します。再割り当てのランタイム ヒットは、この数回で十分に小さいため、心配する必要はありませんが、必要なサイズを完全にオーバーシュートする可能性が高くなります。
于 2009-09-15T02:27:43.680 に答える
3
異常なサイズのメモリブロックを割り当てる場合、そのブロックの割り当てが解除されると（サイズを変更するか、GCが実行されるため）、メモリに異常なサイズの穴ができて、頭痛の種になる可能性があります。メモリマネージャー。したがって、通常は2の累乗でメモリを割り当てることが推奨されます。場合によっては、基盤となるメモリマネージャーが特定のサイズのブロックのみを提供し、奇妙なサイズを要求すると、次に大きいサイズに切り上げられます。したがって、470ユニットを要求するのではなく、とにかく512を取り戻し、要求した470をすべて使用した後でサイズを変更するのではなく、最初に512を要求する方がよいでしょう。
于 2009-09-15T02:51:41.627 に答える
2
VectorおよびArrayListの Java 固有の実装について質問している場合、展開ごとに必ずしも 2 倍になるとは限りません。
ベクターの Javadoc から:
capacity各ベクトルは、および を維持することにより、ストレージ管理を最適化しようとしcapacityIncrementます。容量は常に少なくともベクトル サイズと同じ大きさです。コンポーネントがベクトルに追加されると、ベクトルのストレージが のサイズのチャンクで増加するため、通常はより大きくなりcapacityIncrementます。アプリケーションは、多数のコンポーネントを挿入する前にベクトルの容量を増やすことができます。これにより、増分再割り当ての量が減少します。
Vector のコンストラクターの 1 つを使用すると、Vector の初期サイズと容量の増分を指定できます。Vector クラスは、 Vector の最小サイズを手動で調整したり、自分で Vector のサイズを変更したりするためのensureCapacity(int minCapacity)とも提供します。setSize(int newSize)
ArrayList クラスは非常に似ています。
各
ArrayListインスタンスには容量があります。容量は、リスト内の要素を格納するために使用される配列のサイズです。常に少なくともリスト サイズと同じ大きさです。要素が ArrayList に追加されると、その容量は自動的に増加します。成長ポリシーの詳細は、要素の追加には一定の償却時間コストがあるという事実以外は指定されていません。
ArrayListアプリケーションは、ensureCapacity 操作を使用して多数の要素を追加する前に、インスタンスの容量を増やすことができます。これにより、増分再割り当ての量が減る場合があります。
ベクトルの一般的な実装について質問している場合は、サイズの増加の選択と、どれだけトレードオフであるかということよりも。一般に、ベクトルは配列によってサポートされます。配列は固定サイズです。いっぱいになったためにベクトルのサイズを変更するには、配列のすべての要素を新しいより大きな配列にコピーする必要があることを意味します。新しい配列を大きくしすぎると、決して使用しないメモリが割り当てられます。小さすぎると、古い配列から新しい大きな配列に要素をコピーするのに時間がかかりすぎる可能性があります。これはあまり頻繁に実行したくない操作です。
于 2009-09-15T02:38:20.727 に答える
2
個人的には恣意的な選択だと思います。基数 2 の代わりに基数 e を使用できます (倍数のサイズを (1+e) で 2 倍にする代わりに)。
ベクトルに大量の変数を追加する場合は、ベースを高くすると有利です (実行するコピーの量を減らすため)。メンバーが avg の場合、ベースが低くても問題なく、オーバーヘッドの量が減るため、速度が上がります。
Base 2 は妥協案です。
于 2009-09-15T05:50:44.910 に答える
-1
すべてが同じ大きなOパフォーマンスプロファイルを持っているため、2倍と3倍または4倍のパフォーマンス上の理由はありません。ただし、絶対的には、通常のシナリオでは2倍にする方がスペース効率が高くなる傾向があります。
于 2009-09-15T02:42:39.173 に答える