C++のstd::vectorにpush_backしていくと、ある領域を確保して、それを超えそうになったらまたある程度ゆとりのある領域を確保するという機構になっています。
２倍だけじゃない - d.y.d. にまとめてありますが、std::vectorや類似するコンテナは2倍ずつ領域を大きくしていくのかと思いきや、1.5倍というのも多いんですね。実際にVC10 beta2で動かしてみると、
#include <iostream> #include <vector> int main() { std::vector<int> v; for(int i = 0; i < 100; i++) { const std::vector<int>::size_type old_cap = v.capacity(); v.push_back(i); const std::vector<int>::size_type new_cap = v.capacity(); if(old_cap < new_cap) std::cout << new_cap << " "; } }
1 2 3 4 6 9 13 19 28 42 63 94 141
なるほど、確かに1.5倍になっているようですね。
上のリンク先に1.5倍である理由の説明が紹介されています。2倍だと今まで確保した領域以外に領域を確保する必要がありますが、1.5倍だと領域を再利用することが可能なんだそうです。これは素晴らしいですね。一般に倍率が黄金比未満なら再利用が可能です。今まで確保した領域を、
S = 1 + r + … + rn-1
今確保している領域を、
T = rn
次に確保する領域を、
U = rn+1
とすると、S ≥ Uなら再利用ができるとします。近似を使って、
rn / (r - 1) ≥ rn+1
r2 - r - 1 ≤ 0
これを解いて、
(0 < ) r ≤ (1 + √5) / 2
というわけです。
なるほど再利用するとメモリの利用効率がよさそうです。では、どの程度よいのでしょうか。Pythonで100万回のpushbackを1.5倍と2倍でシミュレートして、領域を確保する直前と直後の点をプロットしました。
r = 1.5 T = 16 S = 0 N = 10 ** 6 while T < N: U = int(T * r) if S >= U: S = S - U + T else: S = S + T print T + 1, ",", S + U print U, ",", S + U T = U
ちょっとこれだとどちらがメモリ効率がいいかわからないですね。そこで、メモリ利用率というものを考えてみましょう。push_backの回数をS+Tで割ったものです。これをグラフにしてみます。
各点を直線で結んでいるのはややおかしいですがあまり気にしないということで。
どうでしょうか。わかりにくいですね。そこで各点のメモリ利用率を単純に平均してみました。そんなに悪くない平均の取り方だと思います。そうすると、
r = 1.5 : 0.382
r = 2.0 : 0.390
変わらない、むしろr = 2のほうが少し利用率がよいくらいですね。r = 2のとき理論的には0.375になり、r = 1.5も最初のほうが少しよいので、結局は同じくらいのようです。r = 1.5のときは、再利用できますが、その手前では効率が悪いのですね。
また、最悪の効率は、r = 1.5とr = 2で0.25とたまたま同じになっています。再利用がされない場合効率は、
(r - 1) / r2
です。これはr = 2のときに最大になります。
結論としては、r = 1.5と2ではメモリ効率は変わらないということになりました。
そうすると、領域確保したときのコピーの回数がr = 1.5のときのほうが大きくなり、その分r = 2のときのほうが有利になると思います。
