MOCK大規模データ対応版

ひとまず完成。MOCKのアルゴリズム自体は変えず、所持するデータと初期化時の最小全域木生成アルゴリズムを変更しました。ただし実行時間とデータ量を両方ともに減らすため、最小全域木の代わりに「準最小全域木」的なものを作り、さらにデータによっては最小全域木を作成できずにエラーになるという仕様なのですが。

メモリ使用量の面では、13,000データで100MB、26,000データで200MBというメモリ使用量になっており、データ数Nに対してO(N)にすることができました。

実行時間の面では、初期化には(おそらく必須の)O(N^2)の処理が含まれているのですが、いままでよりはかなり高速になりました。いままで自身に近いものから順に自身以外のデータのIDをならべた配列をすべてのデータについて作っており、そこでO(N^2*logN)のコストがかかっていたのですが、これをTop M個(Mはパラメータ)だけしか計測しないようにしてO(N*logN)にしたので。13,000個のデータで45分くらいかかってたのが、これが数分で終わるようになりました。ただし距離情報はいっさい持たないことにしたので、GAの評価部分は処理が数倍おそくなりました。まぁでもオーダーはO(N)でかわらないので大丈夫でしょう。


いまの仕様では、データとパラメータMの数値によって実行できたりできなかったりするのですが、こいつを実行時間を増やして解決するのかメモリ使用量を増やして解決するのかかは、今後の課題にしておこうと思います。とりあえず僕がクラスタリングしたいデータを見てみないことには、どっちがいいかは決められないので。(実行時間で解決する方法は現状の問題を理論的には100%解決可能ですが、実時間内に解けるかどうか。。。メモリ使用量で解決する方法は理論的に100%解決可能ではないですが、予備実験で最適なパラメータMを見つけられさえすればOK。)

ふぅ〜、これでひとまず10〜20万件くらいまでなら扱えるようになったかなぁ?