|
|
/*========================================================*/ ＜＜＜あゆしゃのＣ言語プログラミング＞＞＞ /*========================================================*/ 第３９６回 AYGO１３ 思考の高速化 発行 ２００３年９月２９日（月曜日） 発行数 約３１００ {magclick} {magclick} /*========================================================*/ はじめに （ 決り文句 ） /*========================================================*/ ・このメールマガジンはまぐまぐさんから発行しています。 ・ジャンルは、マルチメディアのプログラム、Ｃ言語です。 ・このメールマガジンは、横６０文字で作成しています。 また、インデントはすべて半角スペース４つで構成しています。 ・ここで扱うプログラムは、C言語と半光年以内のものです。 ・登録解除は、まぐまぐさんのホームページでお願いします。 ・まぐまぐさんのバックナンバー（下欄参照）を活用して下さい。 ・ここは私の復習の場です。内容は約１ヶ月内外に私が勉強した 内容になっています。最新の技術があれば、へたれもあります。 ・わかりやすさを優先させる為、たまに嘘があるかもしれません。 /*========================================================*/ ご挨拶 /*========================================================*/ こんにちは。あゆしゃです。 テストの結果が判明しました。１４５点です。 ・・・１００点満点じゃないの？ 専務「なに言ってんの、１５０満点だよ」 ・・・知らなかった（笑） というわけで、１５０点満点中１３５点合格、１４５点なので 見事合格という結果になりました。 １ヶ月もメルマガを占領した甲斐があったというものです。 /*========================================================*/ しかし。 専務「SCJD、受けてみない？」 と、言われました。 SCJDというのは、Javaの上級者（プロジェクト管理クラス）の 資格です。 サン・サーチフィード・Java・デベロッパの略、だったかな。 めちゃくちゃ難しい、ということで、会社ではこの資格の取得に ３０万円の懸賞金を賭けているほどです。 数人受かっているので、まだ懸賞金が有効かどうかは不明です。 面倒なのは嫌いなので、断りたかったのですが、そのときは 祝いの席であり、しかも「御前」であったため、めったなこと がいえず（＾＾）、 「考えておきます」 と、答えておきました。 ・・・考えなあかん。。。 {magclick} /*========================================================*/ 今回のお題 ＜＜ AYGO１３ 思考の高速化 ＞＞ /*========================================================*/ 前回の訂正によって、前々回よりも馬鹿になり、さらに処理速度 が遅くなってしまいました。 今回は、処理速度の底上げを考えて見ます。 /*========================================================*/ まずは、現状ではどれほどの時間がかかるか、計ってみました。 単位は秒、timeGetTime()による計測です。 第２手 74.998 第４手 97.020 第６手 116.868 第８手 135.335 第10手 152.990 第12手 168.532 手数を重ねるごとに、思考時間が増えていきます。 手数を重ねると手を考える範囲が狭くなるので、思考回数は 少なくなり、逆に早くなる気がするのですが、変ですね。 COM、敵、COMの手までしか考えていないので、この手数で、 石を取る判定の処理が重い、ということも考えられません。 石が増えて計算が重くなる、といえば、やっぱり、パワーマップ の計算関係ですね。 /*========================================================*/ とりあえず、１つ変えてみましょう。 // 修正前 // パワーマップの合計を計算 int make_power_total( void ) { int ret = 0; for( int x = 0; x < num; x++ ) { for( int y = 0; y < num; y++ ) { if( board[ x ][ y ] ) continue; if( power_board[ x ][ y ] < -2 ) ret -= 2; else if( power_board[ x ][ y ] > 2 ) ret += 2; else ret += power_board[ x ][ y ]; } } return ret; } // 修正後 // パワーマップの合計を計算 int make_power_total( void ) { int ret = 0; char* pb = board[ 0 ]; int* pp = power_board[ 0 ]; int cnt = num * num; while( cnt-- ) { if( ! *pb ) { if( *pp < -2 ) ret -= 2; else if( *pp > 2 ) ret += 2; else ret += *pp; } pb++, pp++; } return ret; } 配列参照をポインタ参照に変えました。 さて、先ほどと同じ計測をしますと。。。 第２手 74.998 -> 68.979 第４手 97.020 -> 90.771 第６手 116.868 -> 111.010 第８手 135.335 -> 130.007 第10手 152.990 -> 147.632 第12手 168.532 -> 163.676 微妙に、早くなりましたね。 計算の最後の集計なので、この修正はそれほど影響度が高く ありませんでした。 /*========================================================*/ でもあとは、パワーマップ計算の中枢に手を入れるしかないで しょう。 // 修正前 // パワーマップのベースを作成 void make_base( int x, int y, int p ) { add_base[ x ][ y ] = p; if( --p > 0 ) { if( x > 0 && board[ x - 1 ][ y ] == 0 && add_base[ x - 1 ][ y ] < p ) make_base( x - 1, y, p ); if( x + 1 < num && board[ x + 1 ][ y ] == 0 && add_base[ x + 1 ][ y ] < p ) make_base( x + 1, y, p ); if( y > 0 && board[ x ][ y - 1 ] == 0 && add_base[ x ][ y - 1 ] < p ) make_base( x, y - 1, p ); if( y + 1 < num && board[ x ][ y + 1 ] == 0 && add_base[ x ][ y + 1 ] < p ) make_base( x, y + 1, p ); } } // 修正後 // パワーマップのベースを作成 void make_base( char* pb, int* pa, int x, int y, int p ) { *pa = p; if( --p > 0 ) { if( x > 0 && pb[ -NUM ] == 0 && pa[ -NUM ] < p ) make_base( pb - NUM, pa - NUM, x - 1, y, p ); if( x + 1 < num && pb[ NUM ] == 0 && pa[ NUM ] < p ) make_base( pb + NUM, pa + NUM, x + 1, y, p ); if( y > 0 && pb[ -1 ] == 0 && pa[ -1 ] < p ) make_base( pb - 1, pa - 1, x, y - 1, p ); if( y + 1 < num && pb[ 1 ] == 0 && pa[ 1 ] < p ) make_base( pb + 1, pa + 1, x, y + 1, p ); } } ２次元配列参照を１次元配列参照に変えました。 配列参照は、驚くほど時間がかかる処理です。 アセンブラを覗くと、良くわかります。 添え字の計算を、一生懸命やるのです。 計算のためにレジスタを消費し、レジスタの利用効率を下げる 効果もあります。 だから配列参照が簡単か、もしくはポインタにすると、速度が 上がるという仕組みです。 さて、先ほどと同じ計測をしますと。。。 第２手 74.998 -> 68.979 -> 60.717 第４手 97.020 -> 90.771 -> 79.084 第６手 116.868 -> 111.010 -> 100.265 第８手 135.335 -> 130.007 -> 114.895 第10手 152.990 -> 147.632 -> 130.368 第12手 168.532 -> 163.676 -> 138.692 ずいぶんと早くなるものですね。 動きっぱなしの処理を修正したので、手数が増えるほどに 高速化の効果が上がっていきます。 /*========================================================*/ しまった、計測中にこのファイルの保存をやってました。。。 一番最後の計測は、気をつけました。 /*========================================================*/ さいごに /*========================================================*/ レンタルビデオで、マトリックスを見ました。 マトリックス、初体験です。 プログラマたるもの、ああなりたいものです！ でも、アニマトリックスは、どうかとおもいました。 よくいって、同人誌みたいな。（ミテクレはいいけど中身が） 同人誌といえば、ゴムゴム海賊団（ワンピースの市販同人誌）を 初体験しました。 まさかゾロとサンジが、あのような関係だったとは、新事実を 知ってしまった感じです。 {magclick} /*========================================================*/ 次回予告 /*========================================================*/ 次回は１０月６日（月曜日）に、第３９７回を送ります。 お題は「AYGO１４ 思考の高速化２」 まだ足りません。 それと、ユーディーのアトリエ攻略にいそがしいので、周一と いたします。 お楽しみに！ /*========================================================*/ 最後の決り文句 /*========================================================*/ このメールマガジンは、まぐまぐさんから発行しています。 このメールマガジンを解除したい場合は、まぐまぐさんをご利用 ください。このメルマガのまぐまぐアイディーは最後にあります。 このメールマガジンには広告が挿入されます。 このメールマガジンの内容に文面の引用はありません。 めーらっくすの場合はめーらっくすの利用方に従ってください。 このメールマガジンの内容は、転用、流用、宣伝、リンク、 雷火事親父対策 なんて大歓迎です。 {magclick} /*========================================================*/ /*========================================================*/ 発行者 あゆしゃ まぐまぐアイディー 0000020674 まぐまぐバックナンバー http://jazz.tegami.com/backnumber/frame.cgi?id=0000020674 あゆしゃの世界 http://ayusya.hp.infoseek.co.jp/ 登録と解除 http://www.mag2.com/m/0000020674.htm ご意見・ご感想・ご質問メール mailto:ayusya@flamenco.plala.or.jp めーらっくす ＜＜まぐより過去ログが見やすいです＞＞ http://www.mailux.com/mm_dsp.php?mm_id=MM3E1AEE285AB4F |