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

非多項式時間
この前作ったマインスイーパのパターン生成プログラムだが、たまにものすごく時間がかかることが分かった。
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が一番速い。
ちゃんと最適化が効いていれば。
スポンサーサイト




fstream::eof()
fstream のメンバ関数 eof() はファイルの終端まで読んだとき true を返す?





ちがああああう!



strcpy_s
VC で strcpy を使ったら安全じゃない可能性があるから strcpy_s を使えと提案された。

だが断る。



できたー
wmaもすくろぼー出来るようになりました。
やったね!



リンクを増やしてみるテスト

ソースコード
とあるソフトウェアがオープンソースだったのでちょっと落としてみた。
C++ で書かれていた訳だが……ソースがキモすぎる。

new して放置すんな!
char buffer[1024]; …… static つけようよ。
API から返ってきたポインタが NULL かどうかくらいチェックしてくれ。
const char* の変数をキャストして読み書き。const ついてる意味分かってる?
std::string の参照カウンタによるメモリ管理を一生懸命動作させないようにがんばるとか、意味不明です。
そこまでするなら自分で文字列クラス作れよwwww こっちの方がめっちゃ簡単にできそう。

まだまだあるけど、よくこんなので動いてるなあ……
……ああ、だからあんなにメモリ食って動作もっさりなのか。
Copyright © あっ!島だ!. all rights reserved.