私が関心が強いのは将棋ソフトですが、それ意外のことでも構いません。
急ぎませんので慌てず回答をお願いします。
一般的な対策
↓に行くほど大変かお金か手間がかかる。
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.仲間をさがす
とりあえず基本方針としては、「コードのサイズを小さくする」でしょうか。
それを達成するには効率的なコードが必要とされるため、自然と不要なコードが減って高速化されます。
一箇所や二箇所では大した効果は望めませんが、ループの中の処理について効率化したり、多くの箇所で同様の効率化を行うことで、
場合によってはかなりの高速化が行われる場合も有ります。
また、最近のコンパイラは最適化によっても高速化を行うことができます。
特にC(++)で開発する場合にVCやICCなどのコンパイラを用いることで高速化が期待できます。
…と、特に開発言語も記述されていないので概念のみを書いてみました。
回答ありがとうございます。
言語は将棋ソフトの場合、ほとんどCかC++です。
アルゴリズム的な事は誰かが書くと思うので、別のアプローチを。
forよりもwhileが早いです。
i=i+1,i+=1よりもi++の方が早いです。
あんまり細かすぎて役に立たないかもしれませんが、
頭の片隅に。
あ、ポイントは要らないです。
回答ありがとうございます。
あまりオススメできない方法から。
C/C++をお使いということであればインラインアセンブラを
利用するという手があります。速くなりますがコードの保守性は
下がります。
http://e-words.jp/w/E382A4E383B3E383A9E382A4E383B3E382A2E382BBE3...
また、演算は極力ビットレベルの計算を行うなどもあります。
例えばビットシフトなど。
http://proger.blog10.fc2.com/blog-entry-62.html
ほかには関数ではなく、defineを使いまくるなどの方法。
ファイルに記録するのではなく、情報はすべてmallocなどでメモリがガツッと確保してそこで行うなどなど。
※終了する際に保存してやる。
よく言われているこですからあまり参考にならないですかね(^^;
回答ありがとうございます
時間が掛かる計算は予め計算して、パラメータと結果の組合せをデータとして保存して置き、プログラム実行時にそれを参照する。
データ部も含めたコードの長さは、実行時に計算する場合に比べ、長くなると思われますが、スピードは上がると思います。
将棋の定石などはこれに当たるかも知れませんね。
回答ありがとうございます。
「定石」は囲碁用語で、将棋では「定跡」と書きます。
当然のことですが、まずはアルゴリズムを徹底的にチューニングしましょう。
次に、C++の場合ですが、仮想関数のような動的な処理は最小限に抑えて、テンプレートを使うなどの方法で、可能なものは静的に解決しましょう。静的に解決できれば、実行時のコストは0になります。
三番目に、例外処理の振る舞いを(内部的な実現方法まで含めて)正しく把握しましょう。自分では例外処理を使っていないつもりでも、コンパイラは例外処理のためのコードを勝手に埋め込みます。例外を送出しない関数には例外指定 throw() を付け、例外処理を行うべき場所で適切に扱うようにしましょう。
四番目に、標準ライブラリを有効活用しましょう。十分にチューニングされた仕様と実装を持つ標準ライブラリは、通常自作の関数より高速です。
最後に、コンパイル結果を可能な限り確認する習慣を付けましょう。これによって、処理系の癖が把握でき、どうすれば効率のよいコードが書けるかが見えてくるはずです。
回答ありがとうございます。
一般的な対策
↓に行くほど大変かお金か手間がかかる。
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.仲間をさがす
回答ありがとうございます。
オセロで昔使ったことありますが、リアルタイムに次の手の計算を
行うのではなく、全パターンの手をあらかじめ計算しデータとして
保持します。
これを木構造で保持し、相手が指した手によって、どの子ノードに
うつるか判断します。
対人間で、難易度の概念があるのであれば
木構造を作成する際に“強さ”の順番にキレイにならべておき、たとえば右方向に移るとCPU優位、左方向にうつると人間優位などと保持しておけば実現できます。
次の手はあらかじめ内部ですべて読み込んでいるわけですから、
相手が指した後、ほぼ一瞬で指し返せることが予想できます。
※データを初回にすべてロードするとなお早そうですが
ローディングに時間がかかりそうな場合は毎回読み込んでも
よいかもしれません。
オセロの場合はパターンがそれほど莫大ではないため可能ですが、将棋でのパターン数は考えただけでも頭が痛くなりそうですね(^^; とはいっても数日、または十数日、そこそこのパワーを持つマシンをフルに計算させれば実現できなくはないと思います。
回答ありがとうございます。
他の方が指摘している『アルゴリズムのチューニング』に含まれる内容ですけど、
『将棋ソフト』と『高速化』の2つの単語からは、『枝刈り』という手法が連想できます。
将棋ソフトなどでは枝刈りが最も高速化に関わる要因になっているはずです。
先の手を予測していくときに『これは良さそうな展開が望めない手だな』と思ったら、その先の展開を考えずにすぐさま別の可能性を考え出す感じになります。
『良さそうではない』と判断するアルゴリズムにも工夫が必要ですが、これが優秀だと高速で賢い将棋ソフトになるのでは、と思います。
1つ1つの計算を高速化するのではなく、そもそもの計算量を少なくするというのが枝刈りのポイントです。
回答ありがとうございます。
>将棋ソフトなどでは枝刈りが最も高速化に関わる要因になっているはずです。
今年「世界コンピュータ将棋選手権」で革命的なことが起こり、全幅探索の『Bonanza』が優勝しました。
一般的な方針
特殊な方針
回答ありがとうございます。
>人間の入力待ち状態でも計算をする。
実用済みです。
回答ありがとうございます。