SSブログ

分割統治法 [C++]

ABAの日記 - 分割統治法の徹底適用
http://d.hatena.ne.jp/ABA/20080417

ひげねこにっき - 実践
http://higeneko.com/diary.php?Date=2008-04-06#Date2008-04-06

汎用的なアルゴリズムがどうとかっていう話じゃなくて、単純に総当り計算しなくていいところはしないようにしましょうって言うだけの話。ただ、これを分割統治法っていうことを知らなかった。自分では結構普通に計算量の計算とか意識してプログラムするので、名前は知らなくても実際にはやってたりすることが多い。(と言い訳)

リンク先のリンク先の例だと、弾と自機の当たり判定をするのに、ブロック分割された範囲にあるものでのみ行うことで計算量を減らすのに成功したようだ。

ソースは不明だが、弾オブジェクトツリーのルートノードを分割数だけ用意して、オブジェクト移動時にノード間移動を処理。その後自機がいるところのノードと総当りチェック。

今回は平面だったが、FPSでは三角錐の中かどうかというところでもうまく使えそうかな。と思ったけどロケランみたいな軌道が遅い場合はどうするんだろ。明らかに遠いオブジェクトと、そうじゃないオブジェクトを区別する方法は結構めんどくさそうだ。球オブジェクトを自分の周りの制空権として考えて、それの中or外でノードを分割すればいいのかな。まあ、FPSで弾幕張ることも無いからゲームシステム次第か。


http://d.hatena.ne.jp/faith_and_brave/20080418/1208499075

いつも猛っているfaith_and_braveさんのところ

この手の話は、プログラマーしかしないのが問題であって、結局商売でやる場合には、欧米流の動けばオッケーとするのが手っ取り早いんじゃないかなぁと思うわけです。現実として、動けばおっけーっていうにもレベルがあって、動かないことが多々あるんですが。

現実問題として、これらの「見えない技術」を見える化するにはどうしたらいいのか。

例えば、領域の開放をするのに

#define SAFE_FREE(ptr) {if(ptr){free(ptr);ptr=NULL;}

というマクロですべて書くというようなことを某所で言ったら、アルゴリズムがちゃんとしてればそんなNULL代入は必要ないしパフォーマンスの低下だ!なんて言われてしまいました。

例えばこうしておくとどういうことが起こるか。
私の経験上、かなりの確率で起きる現象ですが
・NULLを入れることで、開放した領域にアクセスしようとするとアクセスバイオレーションが発生してバグが見つかる。

 そもそも、ちゃんと動いてたら私は仕事しなくていいわけです。ちゃんと動いてないからこそ、こういう小技でバグをあぶりだす。これは私が動いてないプロジェクトばかり担当してきたから、そういう老婆心が染み付いてきてるんですが、上のような考えの人はコンセプトだけ作って、あとは私のような人に丸投げすることが多いんですよね。だから上のようなこと言いいたいのは、「やるのは勝手だが俺のそばに来るな。自分のケツは自分で拭け」になります。

よくあるのが文字列で例えば以下の場合を考えて見ます。

int copystring( **dst,*src ) { int len = strlen(src); *dst = malloc(len); strcpy( *dst,src ); return len; }


これはいくつか問題点があります。

・srcのNULLチェックが無い
・lenが0のとき、大きすぎるときのチェックが無い
・バッファが確保されなかった場合のチェックが無い

 例えば、アルゴリズム的にこれで問題なかったとしましょう。しかし、将来的に外部の仕様が変更になった、もしくは思っていた仕様とは違っていた、という場合、これらがバグの引き金になることは容易に想像できます。私はそういうことまで含めてプログラミングをするように心がけているのですが、そうじゃない人に説明するのは一苦労です。そういう人はこのコードをコピペしてばらまいてたりもしますが・・・

 あと、もう一つすごく重要なことですが、エラー処理を追加したときに、必ずログを出すようにすることです。アルゴリズムとして明確に起きるエラーで無い限り(例えばファイルが存在しないエラー)必ずログに出すようにします。これをやらないと、誰が悪いのかわからなくなります。世の中ハードを雑に扱ったり、無知ゆえに間違った使い方をする人がいっぱいいます。ただ「動かない」のではなく、「~~というエラーで動かない」ということを、周りの人にわからせないと、すべての責任がプログラマーに集中します。これはなんとしても回避しなければなりません。

 で、こういうのをやったとして、これらによってどれぐらい効果があったかと言われると、明確に数字では表現できないんですよ。だって「動いて当然だけど動いてなかった」のを動くようにしただけですから、最初の計画の数字に入ってないんですよ。そもそもバグは想定外で起きるので、計画に入れない人が多い。

 明確にやろうとすると、バグが何件発生して、何件修正された、みたいなバグトラッキングシステムみたいなことになりますが、技術うんぬんって話じゃないんですよね。やりたいことを現実的な範囲で実装する能力というのは、やって当たり前で、失敗するとできる人のほうへ飛ぶだけだったりして、やっぱり評価されない。そして、無謀な計画を立てる人の給料のほうが高い。プログラマーとしてうまく立ち回るのはなかなか難しいものです。


nice!(0)  コメント(1)  トラックバック(0) 
共通テーマ:パソコン・インターネット

nice! 0

コメント 1

NO NAME

freeはNULL渡しても何もしない保証がありますよ。
by NO NAME (2011-02-26 00:41) 

コメントを書く

お名前:
URL:
コメント:
画像認証:
下の画像に表示されている文字を入力してください。

トラックバック 0

この広告は前回の更新から一定期間経過したブログに表示されています。更新すると自動で解除されます。