高精細Virtual Starへの道
渋谷行きの電車でpset, rect, circle, ringまで作って、帰りで回転を使わずに正五角形の各頂点を描くところまでできた。
で、次は有理数ライブラリをつくるかーと思ったら作らなくてもあった: Boost Rational Number Library
いちいちpairとか作ったら遅いかなぁとか思ったけど、早すぎる最適化は諸悪の根源だな。 void add(const rat &a0, const rat &b0, const rat &a1, const rat &b1, rat &reta, rat &retb)とかやってるけどやめよう。
まちがってるんだけどこれはこれでいい。
さらに間違っている。
でけたでけた。高速化していないけど3分くらいかかるけど。これは2000x2000で出力してプレビューが縮小するのにまかせてある。
回転しようとしたらばぐった！これはこれでよい。
構図の調整。
計算間違いを1回して、計算があったけど今度は「2世代目の円の頭がちょうど上の辺に接する」という設計より「2世代目の円のまわりにできる五角形の頭がちょうど上の辺に接する」の方がきれいであることに気がついて(実際描いてみると五角形の頭が欠けてしまって美しくない)式を立て直して計算して三度目の正直。左下隅は極限の五角形の足であわせてある。
1/4サイズの8回再帰で1秒、9回で4秒、10回で2分30秒。描画される円の数は6倍ずつ増えるので10回はスラッシングが原因で遅くなっているんだと思われ。じゃあvectorで作ってきたけどsetに変えるか。
8回再帰で1分経っても終わらないくらい低速化した。ダメダメですな。ここでhash_setとか使うといいのかなぁ。8回再帰の段階で対象オブジェクトが40万個くらいあるのでなんだかんだでコスト高いんだなぁ。
プロファイラ掛けてみたけど純粋に計算が重い。Rationalをこの目的に特化したもので差し替えて1割速くなるかどうか…
寝て起きて、setがそんなに遅いはずがないと確認してみたら
for(set<g2d>::iterator it=cur.begin(), end=cur.end(); it != end; ++i){
絶賛無限ループでした。修正したら10回再帰で12秒で終わるようになった。
next.size(): 5 next.size(): 20 next.size(): 70 next.size(): 226 next.size(): 685 next.size(): 1995 next.size(): 5625 next.size(): 15516 next.size(): 42120 next.size(): 113070
最終的に一番末端の円は9765625個から113070個に削減されたことになる。
