どこまでが「効率化」？

[ryu]

お初です。

STGにおいて、「弾が発射されているか」や「敵が画面内にいるか」といったフラグのチェックは膨大な回数行っているかと思います。
公開されているプログラムでは、敵の弾を描写するだけでも「敵の最大出現数」*「一体の敵が撃てる最大弾数」という全組み合わせのフラグチェックを行っています。
それを見て思うのですが、「フラグチェックは効率化すべき」なのでしょうか？

たとえば、「出現していない敵」と「出現している敵」、「発射されている弾」と「発射されていない弾」を綺麗に住み分けられるとすれば、弾の描写はもちろん「出現している敵」の「発射されている弾」のみを見ればいいわけです。
そうなれば効率化に繋がると思いますが、ソースもまた難解複雑になるでしょう。拡張性も狭まり、その後の改編も苦労することになります。
その点、公開されているプログラムは不特定多数の閲覧者のために明快かつ確実なプログラムで、だけど原始的です。
機械に任せる仕事なのだから原始的なプログラムでも充分、ということは多々ありますが、環境が変われば動作も繊細に変わります。ある環境では通常通りに動作するプログラムも、少しスペックの低い環境では動作が不充分である可能性も中には存在します。60.0fps丁度で安定していた動作が59.0fpsまでが限界になるかもしれません。その原因がフラグチェックの過多で、そこの効率化を図れば0.1fps分の利益を得るかもしれません。
そういったことがあるとしたら、フラグチェック（だけに括らずとも、その他細かな処理まで）にも工夫を施すべきなのでしょうか。それとも、僅かな利益のためにソースを複雑にするのは効率化ではなく改悪なのでしょうか。

変な質問かと思いますが、多くの意見を聞きたくなったので……。
みなさんはどう思いますか？

[Justy]

＞フラグチェック（だけに括らずとも、その他細かな処理まで）にも工夫を施すべきなのでしょうか。

　ボトルネックになっているところがどこかなのか（全体の処理時間のうち、
どの関数の処理が多く使われているのか、一番多く呼ばれている関数は何かなど）を
調べた上で、そこを改善すれば一定以上の向上が見込めるところに
ついてだけにした方がいいでしょう。

　枝葉な細かな処理をちょっと効率よくしたからといって、そうそう全体が速くなる
わけではないですから。

パレードの法則「プログラムの処理にかかる時間の80%はコード全体の20%の部分が占める」
ttp://ja.wikipedia.org/wiki/%E3%83%91%E3%83%AC%E3%83%BC%E3%83%88%E3%81%AE%E6%B3%95%E5%89%87



＞弾の描写はもちろん「出現している敵」の「発射されている弾」のみを見ればいいわけです。
＞そうなれば効率化に繋がると思いますが、ソースもまた難解複雑になるでしょう。
＞拡張性も狭まり、その後の改編も苦労することになります。

　それは書き方、改善の仕方次第だと思うのですが、もしそうなるのであれば
メリットとデメリットを考えてデメリットが大きければその部位の修正は
止めるべきでしょうね。

　とはいえ、ゲームとかではよく性能をフルに出すためにある程度の保守性・拡張性を
犠牲にして、高速化を求めることも多々ありますので、一概にはいえませんが。



＞「フラグチェックは効率化すべき」なのでしょうか？

　龍神録の館のコードのフラグチェックだけに限っていってしまえば、
チェック総数が非常識な数になっていなければ必要ないように思います。

　でも、そうですね。
　今現在使用している配列の最大インデックス数くらいは覚えておくといいかもしれません。

　例えば配列が 10000の要素あったとしても、実際に使われている配列が
{ 0, 1, 5, 8, 14 } の５つだけだとしたら、14という数字さえを覚えておけば
15以降の残りの 9985個は使われていないことがわかるので、スキップできます。

[Dixq (管理人)]

色々と効率化は出来るには出来ると思います。
線形リストを使うとか、ベクターを使うとか。
配列だとどうしても、0～10まで弾を登録したあと、例えば2番と8番の弾が画面外に出たとき2,8は穴の開いたような状態になり、無駄が出来ます。
しかし毎回穴の空いた部分を詰める処理をすると逆に非効率な気がします。

私は本物の龍神録の中ではJustyさんが仰っているように「登録されている最大数」を弾幕情報に格納し、その番号までチェックしています。
具体的にどれ位計算時間が違うのか試していないのですが、結局色々考えた結果シンプルに配列にしました。
弾が非常に多く出てくる場面では、かなり頻繁にフラグのオンオフが繰り返されるので、
配列のままでいいかなと。
まぁこれだとどうしてもグローバル変数にドカンと結構な容量取ってしまうので、その点ネックですが。

ただ、この辺って思ったより重要じゃない場合が多いみたいなんですよね。
色んなパソコンでテストプレイして見たところ、今のCPUは非常に優秀で、１秒に１億回位の計算は簡単にやってしまうので
大してこの辺効率化したからって全体的に軽くなったと感じない場合が多いみたいです。
それより重い原因はグラフィックにあるようです。

なので館ではあえて効率的にはせずわかりやすさ重視で書いています。

・・とは言え、バックで画面キャプチャソフトを動かしている場合なども考えられるので効率化するにこしたことはないですけどね。

龍神録で一番無駄な処理をしているのは、弾の階層わけ描画ですね・・。
館では紹介していませんが、弾って階層にわけて描画する必要があるんです。
例えば大玉の下に小玉が隠れていると、理不尽死にしてしまう場合があります。
大きな弾は常に下に描画しないといけません。
そこで龍神録では弾の種類番号を大きさ順に並べ、ループのカウンタ番号がその番号になったら描画するようにしています。
なので、普段行っている計算量 X 弾の種類　になるので相当な数になっています。
具体的には

for(t=0; t<弾の種類の最大数; t++){

		/* 登録されている弾幕の、登録されている弾を描画 */
		for(i=0; i<弾幕の総数; i++){
			if(弾幕.フラグ == オン){
				for(s=0; s<登録されている弾の総数; s++){
					if(弾幕.弾.フラグ == オン){
						if(弾幕.弾.種類 == t){
							//描画;
						}
					}
				}
			}
		}

	}

　
黄色の部分が館で紹介している描画の仕方ですよね。
これに弾の種類数を乗算した回数の計算が必要になります。
つまりt=0の弾の種類番号が最も大きく、tの数が大きい種類番号ほど小さい弾の画像になっています。

登録されている弾の種類番号別に最大数を保存しておけば少しはましになりそうですが、
いまいちこれといったすっきりした効率化手段は考え付いていません・・。

[たかぎ]

> 僅かな利益のためにソースを複雑にするのは効率化ではなく改悪なのでしょうか。

すでに回答が出ていますが、（アプリケーションレベルでは）ボトルネックになるところを調べて、そこを集中的に最適化するほうが得策です。「時期尚早な最適化」は諸悪の根源でしかありません。
ライブラリの場合は若干事情が異なりますが、可読性を落としてまで何でもかんでも最適化すべきでないのは同じです。

一方で、特に可読性が低下するわけでもないのに、わざわざ効率の悪い書き方をするのは「時期尚早な不最適化」です。
例えば、ソートに関しては、利用可能な状況では std::sort を使うべきで、わざわざ効率の悪い qsort を使うのは得策ではありません。ましてや、バブルソートを自分で実装するのは最悪です。

フラグに関しても同じことがいえます。
ビット演算や論理演算で簡潔に書けるところを、if文の連続で書くのは得策とはいえません。
仮にブール代数が不得意だからif文の連続にするというのであれば、真のボトルネックは数学が不得意な点にあります。

[Dixq (管理人)]

Justyさんの御書きになった{ 0, 1, 5, 8, 14 }を見て思ったのですが、弾の軌道計算の部分で、何番の弾が登録されてるかも同時に調べてその番号を格納すればいいかもしれません。

0, 1, 5, 8, 14の弾が今登録されてるなら0, 1, 5, 8, 14という番号を他の配列にいれ、その配列の値を配列番号に指定すればイフ文がいらなくなりますね。

[VARIO]

LP_solveというフリーの最適化ソフトをCの中でライブラリとして使う方法について質問です。

http://blog.goo.ne.jp/cat_in_boots/e/bf ... 6aee49a7a0
http://canismajoris.blog79.fc2.com/blog-entry-49.html

を参考に試してみたのですが、環境が違うせいかコンパイルが上手くいきません。
必要なヘッダファイルは入れてあるつもりです。
私のPCの環境はWindows Vista/Visual C++です。
もしかして、UNIX上じゃないと無理なんでしょうか？

参考となるWebサイトでも構いませんので、教えてください。よろしくお願いします。
また、LP_solveの他に、Cの中でLPを解く方法があれば、そちらも併せて教えて頂けると助かります。

[Mist]

> なお、想定している計算機環境は、以下の通りです。
> ・Linux (debian) カーネル2.4
> ・gcc (g++) version 2.95.4
> ・lp_solve 4.0

って書いてあるからWindows環境でやるならCygwinをインストールするとかしないと無理じゃないですか。

[box]

> を参考に試してみたのですが、環境が違うせいかコンパイルが上手くいきません。

そういう場合は、さしあたり、コンパイル時に出たエラーメッセージの全文を
コピー＆ペーストしてみるとよいでしょう。

実は、「うまくいきません」とだけ言うのは、
「何も言っていない」のと同じことだったりします。

[VARIO]

回答ありがとうございます。

では、Cのプログラムから外部のlp_solve.exeを実行する、ということは可能でしょうか？

具体的には、
Cにより制約式を作成し、seiyaku.txtを出力する。(ここまではできています。)
↓
このseiyaku.txtをlp_solve.exeに読み込ませ、最適化を行い、
kekka.txtに出力を行う。

この一連の動作を全てCで行いたいのです。

lp_solve.exeは、通常、
c:\lp_solve.exe < c:\seiyaku.txt > c:\kekka.txt
のようにコマンドプロンプトで実行するプログラムです。

[たかぎ]

> 参考となるWebサイトでも構いませんので、教えてください。

http://okwave.jp/qa4540266.html
http://dixq.net/board/board.html
http://help.okwave.jp/okwave/beginner/netiquette.html

[VARIO]

>>たかぎさん

すみませんでした。重複の質問は削除しました。
困ってるので、よろしくお願いします。

[Justy]

　Windows (VisualC++)用ありましたよ、一緒のところに。
　それを使えばいいんじゃないですか？

[VARIO]

>>ハッカーさん
一緒のところとはどこでしょうか？？
見落としてしまってすみません。

[toyo]

lp_solve_5.5.0.13_source.tar.gz
の中という意味ではないでしょうか（一緒のところ）
dll用とexe用のプロジェクトがありました
http://sourceforge.net/project/showfile ... _id=159735

[toyo]

lp_solve_5.5.0.13_dev.zip
これに作成済みのWindows用ライブラリがあるのでこれを使うのが良さそうです

[VARIO]

皆さんありがとうございます。
ご指導の通り、Windows用ライブラリをインクルードしてみたのですが、


c:\program files\microsoft sdks\windows\v6.0a\include\basetsd.h(434) : warning C4005: 'MAXUINT32' : マクロが再定義されました。
c:\program files\microsoft visual studio 9.0\vc\include\lp_types.h(55) : 'MAXUINT32' の前の定義を確認してください
c:\program files\microsoft sdks\windows\v6.0a\include\basetsd.h(435) : warning C4005: 'MAXINT32' : マクロが再定義されました。
c:\program files\microsoft visual studio 9.0\vc\include\lp_types.h(52) : 'MAXINT32' の前の定義を確認してください
c:\program files\microsoft sdks\windows\v6.0a\include\basetsd.h(438) : warning C4005: 'MAXUINT64' : マクロが再定義されました。
c:\program files\microsoft visual studio 9.0\vc\include\lp_types.h(67) : 'MAXUINT64' の前の定義を確認してください
c:\program files\microsoft sdks\windows\v6.0a\include\basetsd.h(439) : warning C4005: 'MAXINT64' : マクロが再定義されました。
c:\program files\microsoft visual studio 9.0\vc\include\lp_types.h(60) : 'MAXINT64' の前の定義を確認してください
リンクしています...
lp_solve.obj : error LNK2019: 未解決の外部シンボル _get_variables@8 が関数 _main で参照されました。
lp_solve.obj : error LNK2019: 未解決の外部シンボル _get_objective@4 が関数 _main で参照されました。
lp_solve.obj : error LNK2019: 未解決の外部シンボル _solve@4 が関数 _main で参照されました。
lp_solve.obj : error LNK2019: 未解決の外部シンボル _add_constraint@20 が関数 _main で参照されました。
lp_solve.obj : error LNK2019: 未解決の外部シンボル _set_maxim@4 が関数 _main で参照されました。
lp_solve.obj : error LNK2019: 未解決の外部シンボル _set_obj_fn@8 が関数 _main で参照されました。
lp_solve.obj : error LNK2019: 未解決の外部シンボル _make_lp@8 が関数 _main で参照されました。
C:\Users\IKEBE_Lab\Documents\Visual Studio 2008\Projects\lp_solve\Debug\lp_solve.exe : fatal error LNK1120: 外部参照 7 が未解決です。


このようなエラーが出てしまいました。
引き続き自力で頑張ってみます。
もし、何か解決策がありましたらご指導お願いします。

[toyo]

ライブラリがリンクされてないようです
プロジェクトのプロパティから「追加の依存ファイル」で追加するかソースファイルに
#pragma comment(lib, "lpsolve55.lib") // dllの場合
等でリンク指定しましょう