2006.04.27

Research

最小全域木(Minimum Spanning Tree)と格闘

普通にやると0(N^3)の計算量になってしまった...orz
O(N*LogN)の計算量で解けるらしいのだが、ヒープが良く分からない。
とりあえずO(N^2)まで頑張って効率化して、今日のところはO(N^2)で勘弁してやることにする。

が、ここでもっと致命的なことが発覚!!
10,000×10,000のdouble型の配列なんてメモリーにのりきらないよ!!!!
最小全域木以前に全データ間の距離がメモリーにのせられない。
初期化処理の最初の段階でスワップが...orz

もちろん適時距離計算すればいいんだけど、それはそれで計算負荷がかかりすぎる。
1万件以上のデータが出てきたらDB使うくらいしか思いつかない。
そして最終的に扱うデータ数は25万件!!

データマイニング、おそるべし...orz