プログラムを高速化させるテクニックを、できるだけわかりやすく説明してください。

私が関心が強いのは将棋ソフトですが、それ意外のことでも構いません。
急ぎませんので慌てず回答をお願いします。

回答の条件
  • 1人2回まで
  • 登録:2006/07/23 22:16:48
  • 終了:2006/07/27 09:14:17

ベストアンサー

id:kurukuru-neko No.6

kurukuru-neko回答回数1844ベストアンサー獲得回数1552006/07/24 00:28:27

ポイント50pt

一般的な対策

↓に行くほど大変かお金か手間がかかる。

1.最適化コンパイラオプションを速度優先にする。

  可能な限りコードがCPUキャシュで動作する

  サイズに収まるサイズにする。

2.可能な限りお金をかけて高性能な

  CPUとRAMを使う。

3.アルゴリズム・データ構造を考える

  将棋の次の手の探索速度と制度の最速のアルゴリズムを

  考える。 但し、将棋には持ち時間があるので最適化

  速度ではなく持ち時間以内に最善の手を考える事。

  

  http://www.kohgakusha.co.jp/books/detail/4-7775-1110-3

  http://www32.ocn.ne.jp/~yss/book.html

4.仲間をさがす

  http://d.hatena.ne.jp/higotakayuki/20050602/p3

id:jyouseki

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

2006/07/24 01:16:42

その他の回答(8件)

id:ratbeta No.1

ratbeta回答回数132ベストアンサー獲得回数92006/07/23 22:41:34

ポイント30pt

とりあえず基本方針としては、「コードのサイズを小さくする」でしょうか。

それを達成するには効率的なコードが必要とされるため、自然と不要なコードが減って高速化されます。

一箇所や二箇所では大した効果は望めませんが、ループの中の処理について効率化したり、多くの箇所で同様の効率化を行うことで、

場合によってはかなりの高速化が行われる場合も有ります。

また、最近のコンパイラは最適化によっても高速化を行うことができます。

特にC(++)で開発する場合にVCやICCなどのコンパイラを用いることで高速化が期待できます。

…と、特に開発言語も記述されていないので概念のみを書いてみました。

id:jyouseki

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

言語は将棋ソフトの場合、ほとんどCかC++です。

2006/07/23 22:55:55
id:m-nisi No.2

m-nisi回答回数159ベストアンサー獲得回数32006/07/23 23:24:14

アルゴリズム的な事は誰かが書くと思うので、別のアプローチを。

forよりもwhileが早いです。

i=i+1,i+=1よりもi++の方が早いです。

あんまり細かすぎて役に立たないかもしれませんが、

頭の片隅に。

あ、ポイントは要らないです。

id:jyouseki

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

2006/07/23 23:26:27
id:katsube No.3

katsube回答回数133ベストアンサー獲得回数72006/07/23 23:45:17

ポイント30pt

あまりオススメできない方法から。

C/C++をお使いということであればインラインアセンブラを

利用するという手があります。速くなりますがコードの保守性は

下がります。

http://e-words.jp/w/E382A4E383B3E383A9E382A4E383B3E382A2E382BBE3...

また、演算は極力ビットレベルの計算を行うなどもあります。

例えばビットシフトなど。

http://proger.blog10.fc2.com/blog-entry-62.html

ほかには関数ではなく、defineを使いまくるなどの方法。

ファイルに記録するのではなく、情報はすべてmallocなどでメモリがガツッと確保してそこで行うなどなど。

 ※終了する際に保存してやる。

よく言われているこですからあまり参考にならないですかね(^^;

id:jyouseki

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

2006/07/24 00:13:14
id:nandedarou No.4

nandedarou回答回数230ベストアンサー獲得回数342006/07/23 23:54:56

ポイント20pt

時間が掛かる計算は予め計算して、パラメータと結果の組合せをデータとして保存して置き、プログラム実行時にそれを参照する。

データ部も含めたコードの長さは、実行時に計算する場合に比べ、長くなると思われますが、スピードは上がると思います。

将棋の定石などはこれに当たるかも知れませんね。

id:jyouseki

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

「定石」は囲碁用語で、将棋では「定跡」と書きます。

2006/07/24 00:39:40
id:takagidotin No.5

takagidotin回答回数37ベストアンサー獲得回数02006/07/24 00:17:35

ポイント30pt

当然のことですが、まずはアルゴリズムを徹底的にチューニングしましょう。

次に、C++の場合ですが、仮想関数のような動的な処理は最小限に抑えて、テンプレートを使うなどの方法で、可能なものは静的に解決しましょう。静的に解決できれば、実行時のコストは0になります。

三番目に、例外処理の振る舞いを(内部的な実現方法まで含めて)正しく把握しましょう。自分では例外処理を使っていないつもりでも、コンパイラは例外処理のためのコードを勝手に埋め込みます。例外を送出しない関数には例外指定 throw() を付け、例外処理を行うべき場所で適切に扱うようにしましょう。

四番目に、標準ライブラリを有効活用しましょう。十分にチューニングされた仕様と実装を持つ標準ライブラリは、通常自作の関数より高速です。

最後に、コンパイル結果を可能な限り確認する習慣を付けましょう。これによって、処理系の癖が把握でき、どうすれば効率のよいコードが書けるかが見えてくるはずです。

id:jyouseki

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

2006/07/24 00:41:31
id:kurukuru-neko No.6

kurukuru-neko回答回数1844ベストアンサー獲得回数1552006/07/24 00:28:27ここでベストアンサー

ポイント50pt

一般的な対策

↓に行くほど大変かお金か手間がかかる。

1.最適化コンパイラオプションを速度優先にする。

  可能な限りコードがCPUキャシュで動作する

  サイズに収まるサイズにする。

2.可能な限りお金をかけて高性能な

  CPUとRAMを使う。

3.アルゴリズム・データ構造を考える

  将棋の次の手の探索速度と制度の最速のアルゴリズムを

  考える。 但し、将棋には持ち時間があるので最適化

  速度ではなく持ち時間以内に最善の手を考える事。

  

  http://www.kohgakusha.co.jp/books/detail/4-7775-1110-3

  http://www32.ocn.ne.jp/~yss/book.html

4.仲間をさがす

  http://d.hatena.ne.jp/higotakayuki/20050602/p3

id:jyouseki

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

2006/07/24 01:16:42
id:katsube No.7

katsube回答回数133ベストアンサー獲得回数72006/07/24 01:58:44

ポイント30pt

オセロで昔使ったことありますが、リアルタイムに次の手の計算を

行うのではなく、全パターンの手をあらかじめ計算しデータとして

保持します。

これを木構造で保持し、相手が指した手によって、どの子ノードに

うつるか判断します。

対人間で、難易度の概念があるのであれば

木構造を作成する際に“強さ”の順番にキレイにならべておき、たとえば右方向に移るとCPU優位、左方向にうつると人間優位などと保持しておけば実現できます。

次の手はあらかじめ内部ですべて読み込んでいるわけですから、

相手が指した後、ほぼ一瞬で指し返せることが予想できます。

 ※データを初回にすべてロードするとなお早そうですが

  ローディングに時間がかかりそうな場合は毎回読み込んでも

  よいかもしれません。

オセロの場合はパターンがそれほど莫大ではないため可能ですが、将棋でのパターン数は考えただけでも頭が痛くなりそうですね(^^; とはいっても数日、または十数日、そこそこのパワーを持つマシンをフルに計算させれば実現できなくはないと思います。

id:jyouseki

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

2006/07/24 02:26:10
id:SiroKuro No.8

SiroKuro回答回数15ベストアンサー獲得回数02006/07/24 02:44:25

ポイント30pt

他の方が指摘している『アルゴリズムのチューニング』に含まれる内容ですけど、

『将棋ソフト』と『高速化』の2つの単語からは、『枝刈り』という手法が連想できます。


将棋ソフトなどでは枝刈りが最も高速化に関わる要因になっているはずです。

先の手を予測していくときに『これは良さそうな展開が望めない手だな』と思ったら、その先の展開を考えずにすぐさま別の可能性を考え出す感じになります。

『良さそうではない』と判断するアルゴリズムにも工夫が必要ですが、これが優秀だと高速で賢い将棋ソフトになるのでは、と思います。


1つ1つの計算を高速化するのではなく、そもそもの計算量を少なくするというのが枝刈りのポイントです。

id:jyouseki

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

>将棋ソフトなどでは枝刈りが最も高速化に関わる要因になっているはずです。

今年「世界コンピュータ将棋選手権」で革命的なことが起こり、全幅探索の『Bonanza』が優勝しました。

2006/07/24 23:38:31
id:apple-eater No.9

apple-eater回答回数420ベストアンサー獲得回数82006/07/24 06:11:30

ポイント30pt

一般的な方針

  1. 関数を使わない。全て埋め込む。
    関数呼び出し時の処理が結構馬鹿にならないので。
  2. ライブラリを使っている場所に注意する。ライブラリを使わずにすむならそれがよい。ライブラリはブラックボックスゆえ高速化の邪魔
  3. I/O出力部に注意する。画面出力、標準入出力など。I/Oは高速化のときのネックとなるから。
  4. 演算はビット単位で行う。たとえば2のべき乗ならシフト演算。
  5. 変数のメモリ配置に気をつかう。メモリアラインがまずいとCPU実行速度に影響する。構造体の設計とか要注意。32ビット境界もしくは64ビット境界にぴったり合わせる。
  6. 浮動小数点演算でなく固定小数点演算にする。つまり整数演算。
  7. 演算せずに表を使う。九九の表のようなもの。

特殊な方針

  1. 人間の入力待ち状態でも計算をする。
  2. 人間入力時、マウス位置を監視して、入力位置を予想し先回り演算。
id:jyouseki

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

>人間の入力待ち状態でも計算をする。

実用済みです。

2006/07/27 09:10:56

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません