« 2007年01月 | メイン | 2007年03月 »
2007年02月19日
動的配列への追加コストはなぜ O(1)?
動的配列への追加コストは O(1) ってのは覚えていればそれだけの話ですが，どうしてかと言われると意外と難しいものです． というのも, このO(1)ってのは動的配列の実装方法に強く依存しているからです．実装を知っていないと答えられません．一般論として，1つ要素を追加するとき，配列に空きがなかったら新しく配列を作り直して全要素をコピーする必要があります．コピーのコストは O(n) だから，追加コストも O(n) になるという議論が混乱の元になっています． こういうときは，要素追加を n 回繰り返したときの計算量を n で割った平均をとるという解析方法が使われるそうです．一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです．
さて，std::vector や perl の配列といったほとんどの動的配列は，足りなくなったら配列を2倍にしていくという 実装が使われています．このアルゴリズムの「ならし解析」をやってみます.
追加を n 回繰り返したとき，配列を倍々にしていくので，コピー(再配置)が起きる回数は log n 回です． 各再配置で 1, 2, 4, 8 .. と要素をコピーするので，全体の総和は
1 + 2 + 4 + 8 + ... 2^(log n) = 2^(log n + 1) - 1 =~ 2n となります．
コピーが発生しない場合の数は n - log(n) =~ n 回です．(log n は無視できる) .
二つを合計すれば，高々 3n の要素がコピーされることになります．これを n で割った値が １つの要素を追加するときの平均的な計算量なので，結果として O(1) が導かれます．一般的に配列サイズを指数的に増やしていけば O(1) になります．
動的配列の実装方法は倍々以外にも考えられます．たとえば，固定長 k だけ逐次増やしていく実装の「ならし解析」はどうなるでしょうか．
再配置が行われる回数: n/k
コピーの要素の数: k + 2k + 3k + ... + n/k * k = k * (1 + 2 + ... + n/k) = k * n/k (1 + n/k) =~ (n^2)/k
1要素の平均計算量: O((n^2)/k) = O(n/k)
なんと! 固定長で増やしていく実装だと，O(n) になってしまいます．
動的配列の要素追加コストが O(1) になるといのは，倍々にしていくという内部の実装があってはじめて言えることです. 逆に言えば，倍々にする理由付けもこの議論から行えます．
2007年02月12日
CRF++ 0.46
CRF++ 0.46 を公開しました．機能的な変更点はございませんが，ライセンスが LGPL/BSD のデュアルライセンスになりました．マニアックなツールですが，いろんなところで使われるみたいです．
2007年02月08日
父親になった
私事で恐縮ですが，1/30 日に長男が生まれました．親バカにはなるまいと誓っていたのですがそんなわけにはいかないようです．さっそくこれにあわせて D80を購入しました．にわかカメラマンです．世間では少子化の話題がひっきりなしですが，父親になったぶん興味深くウォッチするようになりました．
2007年02月07日
ソートの平均要素移動距離
配列をソートする際に各要素の平均移動距離はどれくらいになるか問題が同僚の間で話題になった. 結論から言ってしまえば，サイズ n の配列の場合平均移動距離は n/3 になるらしい．サイズ n の場合, 最右の要素は [0 .. n-1] に等確率で移動するので，直感的に考えると n/2 のような気がする．しかし，真ん中の要素は両側に移動するので，その距離は小さくなる．平均移動距離は n/2 より小さい値になるはずだ.
頭で考えるより手を動かしたほうが楽なので，モンテカルロサンプリングしてみた. 配列をランダムにシャッフルし，ソート済みの配列と比較して各要素の平均移動距離を求める．これを 1000 回繰り返し平均値を計算する.
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
static const size_t size = 1000;
static const size_t max_trial = 1000;
int main() {
std::vector<int> ary(size);
for (int i = 0; i < size; ++i) ary[i] = i;
size_t sum = 0;
size_t trial = 0;
for (int n = 0; n < max_trial; ++n) {
std::random_shuffle(ary.begin(), ary.end());
for (int i = 0; i < size; ++i) {
sum += std::abs(ary[i] - i);
++trial;
}
}
std::cout << static_cast<float>(1.0 * sum / trial / size) << std::endl;
}
ivy:~% c++ -O3 foo.cpp ivy:~% ./a.out 0.33348すばらしい．確かに 1/3 というのは正しいようだ.
まだしっくりこないので，数学的に証明してみる.
サイズ n の配列のインデックス [0, 1, 2 ... k, ... n-2, n-1] を考える．各要素は等確率 1/n で別の要素に移動する．インデックス k の平均移動距離は左側と右側で場合わけしてかんがえると
左側の要素 L(k) = k/n + (k-1)/n + ... + 1/n + 0/n = k * (k + 1) / 2n
右側の要素 R(k) = 1/n + 2/n + .... + (n - k - 1)/n = (n - k - 1) * (n - k) / 2n
となる.
平均移動距離は k を 0..n-1 まで動かして足し合わせて，n で割ればいい． (平均移動距離 = [\sum_{k=0..n} L(k) + R(k)] / n). ここでは漸近的な振る舞いだけ分かればいいので，R(k) + L(k) の最大次数の項だけみて級数和を積分で置き換えてもかまわない.
[R(k) + L(k)]/n の最大次数は L(k)/n の k^2 / 2n^2, R(k)/n の k^2 / 2n^2 を足し合わせて k^2 / n^2 となる． これを k = 0..n の区間で積分すればいいので，n^3/3(n^2) = n/3 になる． (∵∫x^2 dx = (x^3)/3) これは n → ∞ の漸近的な振る舞いなので，n が小さいときは余剰項の影響をうける．
ということでスッキリ!