Hatena::Grouptopcoder

chokudaiの日記

 | 

2010-04-14

MarathonMatch58 参加記その2

| 02:16 | MarathonMatch58 参加記その2 - chokudaiの日記 を含むブックマーク はてなブックマーク - MarathonMatch58 参加記その2 - chokudaiの日記 MarathonMatch58 参加記その2 - chokudaiの日記 のブックマークコメント

さて、ここから埋め込み対決です

埋め込みデータをどう使うか

他のデータを再利用

2次元データで上下が抑えられたからといって、それで満足してちゃもったいない!ということで、存在するデータは全て使います!

上下がわかったので、その範囲に入っている、埋め込みデータ全てに対して、狭い範囲で動作するかどうか確かめて見ると、大体途中で引っかかります。埋め込みデータ強い!まぁちょっと範囲が違っても、素数の密度が薄い場所をメモってくれてるんだから正しいと思う

このことから、時間内にランダムの焼きなまし的手法は完全に捨てても良い程度であることが確認できます。この当たりで正直「クソゲー」と思っちゃってたりもしました。

埋め込みデータ作成の高速化

広範囲に対するエラトステネスで一気に篩う

本番データでは、ある程度大きい数字になるとミラーラビンのほうが早くなる範囲が存在しますが、埋め込みデータは1億程度の範囲を一辺に調べたほうが効率が良いので、圧倒的にエラトステネスのが早いです。篩なめんな!

Cによる高速化

ここまで埋め込み勝負だとC#で作ったのはさすがに不利かなぁ、ということでCでデータ出力をさせてました。これは、「他の環境でも動かせること」も視野に入れて作ってたんだけど、結局動かせず

CUDAによる高速化

・・・調べてたけど出来なかったよ!w

データの格納方法

上記のように2次元配列の全体を結局使うんだったら、上から押さえたりしたから押さえたりができなくなるけれども、それでも1次元で重複なしでずらーっと並べたほうが、特徴点をもっとたくさん使えたのではないか?という疑問が発生

とりあえず、「今回のデータの格納方式から溢れるけれども、有効な特徴点」ってのを適当に拾い集めたら、微妙に点数がアップ 本当に微妙にだけど

上位の人はこれをやってそうだなーって感じはした

終了後考察

データの格納方法変更について

上位陣はやはり上記の格納方法を使っていた・・・んだけど、下にも書いたとおりやっぱり殆ど影響はなかったみたい。データの調査数の差が大きい

そもそも、自分のデータの調査数では、2次元で格納してて重複が大量発生することで発生するデメリットが感じられない程度に足りなかった、ってのもあるのかもしれない。ぶっちゃけ重複たくさんっていうのはそれだけ圧倒的に密度が薄い場所があるってことで、それならそんなに特徴点は多くない、って予想は大体正しかったみたい。

エラトステネスの範囲

KOTEHOK氏なんかはエラトステネスを自分よりかなり広範囲で最初にやってた模様。そもそもエラトステネスが自分のアトキンより早い!?みたいなのもあるんですが、それは言語差っぽいので保留w

狭い範囲においては自分の実験データだとミラーラビンのが早い、ってのが出てるんだけど、KOTEHOK氏の環境だとそうでもないのかなぁ、うーん?

データの調べた量

1位のKOTEHOK氏のデータ・2位のnamiajelszo氏のデータを自分のデータに流し込んでみると、主要な部分は1割残りませんでした><

ということで、検索できてる範囲がまるで違うみたい。(ついでに言えば、これを流し込めばほぼ同様のパフォーマンスが今の少し効率の悪いデータ格納方法でも十分に出せることも確認)

ということで埋め込み速度・スペック差が大きかったのかなぁ、っていうのが正直な感想です。くそげー!ばか!っていっちゃだめですか!

検索順序

小さいところでだいぶ落としてたみたいで、これは単純に小さい数字から試した数が足りなかったみたい。(6日くらいやったけど!)

もうちょっとそっちを重視するべきだった?他の人のソース見ると完全にそろってるところで、自分はそこまで調べてないよ!って奴が多いから、そうとしか考えられない

まとめ

8位以内は綺麗に埋め込みゲーだったんじゃないかなぁ、と思います。それより下の人は、埋め込む十分な時間がなかったか、何か足りなかったか、ってイメージです。(30位までのソースコードは一応目を通しましたが、見落とし大量にあると思います><)

それ以上は・・・スペック差じゃないのこれ!ばか!って言いたいけど、並列化とかが出来てない時点で自分の手数の足りなさが響いたのかも?埋め込みゲーは初めてだったから、これだけ点数が取れればむしろ十分かもしれない

Result

6位/375 Rating 2392 -> 2444

まぁこんなもんかなぁ、と思います。最終で2つ順位落ちちゃったけど

 |