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)でかわらないので大丈夫でしょう。

Read more

Amazon.co.jp: バッテリー 3: 本: あさの あつこ

photo
バッテリー 3 (角川文庫)
あさの あつこ
角川書店 2004-12-26
売り上げランキング : 6597
おすすめ平均 star
starこの巻で挫折
starややストリーに不自然さを感じますが、面白いですよ
starちょっと残念
star一気読み
star青波の言葉がとても美しい

バッテリー〈4〉 (角川文庫) バッテリー〈2〉 (角川文庫) バッテリー〈5〉 (角川文庫) バッテリー (角川文庫) バッテリー 6 (6) (角川文庫 あ 42-6)

by G-Tools , 2008/09/12

すっかりはまってしまった。
最近はプログラム書いてばかりの毎日ですが、一晩で読み終えてしまいました。