20

std :: vectorの後ろ（push_back）での挿入の分析をどのように行いますか？償却時間は挿入ごとにO（1）です。特に、Stephan T Lavavejによるchannel9のビデオと、これ（17:42以降）で、Microsoftがこのメソッドを実装すると、ベクトルの容量が約1.5増加すると彼は述べています。

この定数はどのように決定されますか？

4

3 に答える 3

20

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

具体的には、定数係数が大きすぎると、平均的なケースのパフォーマンスは良好になりますが、特に配列が大きくなると、最悪のケースのパフォーマンスは低下します。たとえば、10001番目の要素がプッシュされているという理由だけで、10000サイズのベクトルを2倍（2x）にすることを想像してみてください。編集：Michael Burrが間接的に指摘したように、ここでの実際のコストは、おそらく、必要以上にメモリを大きくすることです。これに加えて、係数が大きすぎる場合に速度に影響を与えるキャッシュの問題があります。必要以上に大きくなると、実際のコスト（メモリと計算）が発生すると言えば十分です。

ただし、定数係数が小さすぎる場合、たとえば（1.1x）の場合、最悪の場合のパフォーマンスは良好になりますが、再割り当てのコストがかかりすぎるため、平均パフォーマンスは低下します。

また、以前の同様の質問に対するJonSkeetの回答を参照してください。 （@Bo Perssonに感謝します）

分析についてもう少し：nあなたが押し戻しているアイテムと。の乗算係数があるとしましょうM。その場合、再割り当ての数はおおよそ（ ）の対数ベースMになります。そして、 3番目の再割り当ては（3乗に）比例するコストになります。その場合、すべてのプッシュバックの合計時間はになります。プッシュバックの数はであるため、この級数（等比数列であり、おおよそ限界まで減少します）を。で割った値になります。これはほぼ定数です。nlog_M(n)iM^iMiM^1 + M^2 + ... M^(log_M(n))n(nM)/(M-1)nM/(M-1)

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

于 2011-07-01T16:37:24.493 に答える
8

あなたはこの種のものがどのように機能するかを理解することを試みるために数学をすることができます。

漸近解析を使用するための一般的な方法は、バンカー法です。あなたがすることは、追加のコストですべての操作をマークアップし、後で高価な操作の代金を支払うために後でそれを「節約」することです。

計算を単純化するために、いくつかのダンプの仮定を立てましょう。

  • 配列への書き込みにはコストがかかります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保存しておくことができます。Kこのお金は、移動するN個の要素すべてに対して支払うことができる必要があるため、との間の関係を理解できます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

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

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

于 2011-07-01T17:19:11.627 に答える
1

ええと、通常の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回の再割り当て（10回の5回の乗算）後のバッファーサイズは10^5です。これは、要素のコピー操作の数よりも約9倍大きくなります。つまり、コピーに費やされる時間は、結果のバッファサイズでほぼ線形になります。

10ではなく2を底にすると、（2 ^ 5-1）/ 1 = 2^5-1になります。

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

乾杯＆hth。

于 2011-07-01T17:06:51.500 に答える