FC2ブログ
まっさらな心を 傷つけないように 約束をしよう

道に
あの……落としものですよ?

         .∧__,,∧
        (´・ω・`)
         (つ枕と)
         `u―u´




……なんでやねん
スポンサーサイト




いろいろ書いてみた
いろいろ書いてみた、というよりちょっとずつ書き溜めてきたもの。
私から見える世界はこんなんです。
なげえ。



非多項式時間
この前作ったマインスイーパのパターン生成プログラムだが、たまにものすごく時間がかかることが分かった。
50ミリ秒未満で終わることもあれば、60秒以上もかかることも。


exe「200万通りくらい調べて、これ以上解けないってことが分かったよ! いっこ減らしてもう一回やってみるね!」
exe「200万通りくらい調べて(ry


なんというアホの子……最初は無限ループかと思ったぜ。

主なアルゴリズムが「解決していない数字の周りの全数探索」なので、運が悪いとこういうことになる。
非多項式時間アルゴリズムは恐ろしいな。



ということで適当に改良。
まずは全数探索をやめて、背理法を使うことにした。
仮定して矛盾が出たら、つまりそれを満たす解がなかったら確定。
でも根本的な解決にはならず、特に矛盾が出る場合には結局全数探索しているのと同じなので安定しない。

次に、時間がかかりそうなときは解くのを諦めて別のパターンを探すようにしてみる。
するとなかなかいい感じになった。上級程度なら max 0.3秒、十分実用可能レベル。
しかもまったく解なしが出ない。

が、盤面が大きくなるとやはり時間がかかる。
64x64に777個の盤面を生成すると、最大48秒、平均11秒もかかった。
でもこれ以上アルゴリズムを改良するのは難しいかな……
共通の未確定部分を持たないように分割して列挙しても、遅くなっただけだし……


あと、VCが遅いとか言ったけど、そんなことはなかったぜ。
プロパティで見ると最適化の欄が「実行速度」になってるのに。
……内部的にはプロジェクトの規定値を継承するってなってて、しかも継承してくれてなかったのでした。
罠過ぎる。
ウィザードに頼らずちゃんとコンパイルオプション見ろってことか……



速かった条件にて適当に計測。マインスイーパ上級。
数字はパターン生成一回あたりの時間(ms)。

bcc: min=15, max=530, average=129.545
gcc: min=0, max=250, average=84.145
VC: min=0, max=250, average=82.47

うむ、なかなか速くなった。
ちゃんと最適化が効いていれば、VCが一番速い。
ちゃんと最適化が効いていれば。
Copyright © あっ!島だ!. all rights reserved.