std :: vector挿入の償却解析

Question

std :: vectorの後ろの挿入（push_back）の解析はどのように行うのですか？償却された時間は挿入あたりO（1）です。特にvideo in channel9 by Stephan T Lavavejとin this (17:42 onwards)では、最適なパフォーマンスのために、この方法をMicrosoftが実装すると、ベクトルの容量が約1.5増加すると言います。

この定数はどのようにして決まりますか？

Answer 1

push_backを意味し、挿入しないと仮定すると、重要な部分は一定の定数（毎回N個以上の要素を取得するのではなく）を掛け合わせたものとみなされ、一定の時間を償却します。係数を変更すると、平均ケースと最悪ケースのパフォーマンスが変わります。

具体的には： 定数が大きすぎると、平均的なケースのパフォーマンスは良好ですが、アレイが大きくなるとパフォーマンスが悪くなります。たとえば、10001番目の要素がプッシュされているという理由だけで、10000サイズのベクトルを倍増（2倍）することを想像してください。編集：マイケルバールが間接的に指摘したように、ここの実際のコストはおそらく、あなたが必要とするよりもはるかに大きなメモリを増やすことでしょう。私はあなたの要因が大きすぎる場合、速度に影響するキャッシュの問題があることをこれに追加します。必要以上に大きく成長すると、実際のコスト（メモリと計算量）があるといっても過言ではありません。

しかし、一定係数が小さすぎると、（1.1x）とすると、ワーストケースのパフォーマンスは良くなりますが、平均パフォーマンスは悪くなります。余分なコストを再配分する必要があるためです回。

Also, see Jon Skeet's answer to a similar question previously.（感謝@Bo Perssonの）

分析についてもう少し：あなたはnあなたが戻って推進しているアイテムとMの増倍率を持っていると言います。その後、再割り当ての回数は、ログベースM（n（log_M(n)））になります。また、再配分は、M^i（Mからiまで）に比例します。その後、すべてのプッシュバックの合計時間はM^1 + M^2 + ... M^(log_M(n))になります。プッシュバックの回数はnであり、このシリーズ（幾何学的なシリーズで、おおよそ(nM)/(M-1)になります）を、nで割ったものです。これはおおよそ一定である、M/(M-1)です。

Mの値が大きい場合は、多くの場合オーバーシュートが発生し、必要以上に多くのリソースを割り当てることになります（前述）。 M（1に近い）の小さな値の場合、この定数はM/(M-1)と大きくなります。この要因は平均時間に直接影響します。

Answer 2

私は通常の10進数のような数字のシステムに精通していると、分析は本当に簡単です。

簡略化のために、現在の容量に達するたびに、新しい10倍の大きなバッファーが割り当てられるとします。

元のバッファのサイズが1の場合、最初の再割り当てで1要素がコピーされ、2番目のバッファには10要素がコピーされます（以降、バッファのサイズは10になります）。したがって、5回の再割り当てでは、1 + 10 + 100 + 1000 + 10000 = 11111の要素コピーが実行されます。 9を掛ければ99999になります。今度は1を加え、100000 = 10^5とする。つまり、逆にすると、5つの再割り当てをサポートするために実行される要素コピーの数は（10^5-1）/ 9になります。

5つの再割り当て後のバッファサイズ（5回の乗算10回）は10^5です。これは、要素コピー操作の数よりも約9倍大きい。つまり、コピーに費やされた時間は結果として得られるバッファーサイズではほぼ線形です。

10の代わりに2を使うと（2^5-1）/ 1 = 2^5-1になります。

他のベース（またはバッファサイズを増やす要因）についても同様です。

乾杯&hth。

Answer 3

あなたはこの種のものがどのように機能するかを調べるために数学を行うことができます。

漸近分析を使用する一般的な方法は、バンカー法です。あなたがすることは、余分なコストですべての操作をマークアップし、後で高価な操作を支払うために後でそれを保存することです。

---

のは、いくつかのダンプ仮定は数学を簡素化するために作ってみましょう：

• 配列費1への書き込み。 （配列間の挿入と移動で同じ）
• 大きな配列の割り当ては自由です。

そして、我々のアルゴリズムは次のようになります。

明らか

function insert(x){ 
    if n_elements >= maximum array size: 
     move all elements to a new array that 
     is K times larger than the current size 
    add x to array 
    n_elements += 1 

我々は新しい配列に要素を移動しなければならないとき、「最悪の場合は、」起こります。挿入コストに一定のマークアップdを追加して、これを償却しようとします。これを操作ごとに合計で(1 + d)にします。

アレイのサイズを変更した直後に、（1/K）が満たされ、お金が保存されません。 配列を書き込むまでには、少なくともd * (1 - 1/K) * Nが保存されます。このお金が移動して、すべてのN個の要素のために支払うことができなければならないので、我々はKとd間の関係を把握することができます：

d*(1 - 1/K)*N = N 
d*(K-1)/K = 1 
d = K/(K-1) 

役立つ表：このからそう

k d  1+d(total insertion cost) 
1.0 inf inf 
1.1 11.0 12.0 
1.5 3.0 4.0 
2.0 2.0 3.0 
3.0 1.5 2.5 
4.0 1.3 2.3 
inf 1.0 2.0 

---

この問題のために時間/メモリのトレードオフがどのように働くかについての大まかな数学者の考えを得ることができます。もちろん、いくつかの注意点があります：要素が少なくなったときに配列を縮小することはしませんでした。これは、要素が削除されず、余分なメモリを割り当てる時間コストが考慮されていない最悪の場合のみをカバーします。

彼らはほとんど私が無関係と書いたもののほとんどを最終的にこれを理解するための一連の実験的テストを実行しました。