ab.com コミュニティ

ActiveBasicを通したコミュニケーション
現在時刻 - 2024年3月29日(金) 04:43

全ての表示時間は UTC+09:00 です




新しいトピックを投稿する  トピックへ返信する  [ 5 件の記事 ] 
作成者 メッセージ
投稿記事Posted: 2009年8月10日(月) 21:43 
連続の投稿をご容赦ください。

前投稿 「Select Case と関数ポインタ」で、色々と試行錯誤をしていたのです。
その際に、Gosubを試しに使用してみたら、関数(Sub~SubEnd)よりも高速なのです。
テストしたコードは以下の通りです。

コード:
#N88BASIC

	Dim P%(8,8) As Integer
	Dim Calc As Integer
	Dim Count As DWord
	Dim CountEnd As DWord
	Dim dwStart As int64
	Dim dwEnd As int64

	CountEnd=50000000

'関数
	dwStart = GetTickCount()
	For Count=1 TO CountEnd
		Ptn01()
	Next
	Timer()

'Gosub
	dwStart = GetTickCount()
	For Count=1 TO CountEnd	
		Gosub *Ptn
	Next
	Timer()

	Input Count
	End

Sub Timer()
	dwEnd = GetTickCount()
	Print (dwEnd-dwStart)/1000 
END Sub

*Ptn
	Calc=((((((P%(1,1)*3+P%(2,1))*3+P%(3,1))*3+P%(4,1))*3+P%(5,1))*3+P%(6,1))*3+P%(7,1))
	Return


Sub Ptn01()
	Calc=((((((P%(1,1)*3+P%(2,1))*3+P%(3,1))*3+P%(4,1))*3+P%(5,1))*3+P%(6,1))*3+P%(7,1))
End Sub
上記の例ですと、50000000回(5千万)ループしています。この場合はGosubの方が高速です。
しかし、200000回(20万)程度のループですとGosubが低速でした。

演算回数を多く繰り返すような場合だと、(処理速度向上を考えると)Gosubを使うべきなのでしょうか?

#時間測定はコレで合っているのでしょうか?


通報する
ページトップ
   
投稿記事Posted: 2009年8月11日(火) 10:29 
オフライン

登録日時: 2005年5月31日(火) 10:52
記事: 264
お住まい: 高知
引用:
> 連続の投稿をご容赦ください。
>
> 前投稿 「Select Case と関数ポインタ」で、色々と試行錯誤をしていたのです。
> その際に、Gosubを試しに使用してみたら、関数(Sub~SubEnd)よりも高速なのです。

> #時間測定はコレで合っているのでしょうか?
計測環境やら条件をよく検討する必要がありますが、
おおむねSub~End Sub < GoSub~Returnの関係になります。

Sub~End Subは関数という機能、
GoSub~Returnは分岐(サブルーチン)命令である
ということは理解されていると思います。

難しい話になりますが、CPUが解釈する機械語で考えた場合、
関数の呼び出しとGoSub~Returnは
プログラムのある位置へ移動してから、もとの位置に戻ってくるという点においては等価です。

ただし、関数の呼び出しの処理は、単純に行って帰ってくるだけではなく、
例えば関数内で使用されるローカル変数の準備など、
単純にGoSub~Returnのように行って帰ってくる訳ではありませんので
その分だけ時間がかかります。
※余談 これを業界用語でオーバーヘッドと呼びます。
スピード狂なプログラマはこの時間に留意して
関数を使う処理と使わない処理を分けるようです。
私の場合は可読性重視なので、ほとんど気にしませんが(笑


これは最初に書いたように、計測条件(パラメータの有無など)によって
かなり違った結果になるので一概に言えませんが、
ほとんどの場合GoSub~Returnの方が速いという結果が得られると思います。

ただ、GoSub~Returnには制限も多いので使いどころに注意してください。

具体的にいうと、関数内でGoSub~Returnは使わないでください。
もしかしたら、AB4でもエラーになるかもしれませんが、
AB5では仕様で使えないことになっていたと思います。


P.S.
そういえば、最初はSelect CaseでSubを呼び出すのをどうやって速くするかという
話題でしたよね。
記事を見たときに返信しようと思っていたんですが、先にtakさんが書かれていたので
放置していたのですが、
あんなに沢山の種類のSubを個別に作成して呼び出す状況を改善した方が
良いのではないでしょうか?
もし、個々のSubに類似したコードが含まれているのでしたら抽象化して
一つのSubにまとめて引数(パラメータ)で処理を分けるようにした方がいいと思いますよ。


通報する
ページトップ
 記事の件名:
投稿記事Posted: 2009年8月11日(火) 12:58 
NoWestさん、返信ありがとうございます。

引用:
例えば関数内で使用されるローカル変数の準備など、
単純にGoSub~Returnのように行って帰ってくる訳ではありませんので
その分だけ時間がかかります。
分かり易い説明でした。なるほど!
確かに、現在のコンピュータからすれば、処理速度に対して「ムキになって」高速化するよりかは、分かり易いプログラムの方が良いでしょうね。
引用:
あんなに沢山の種類のSubを個別に作成して呼び出す状況を改善した方が
良いのではないでしょうか?
えーと、お恥ずかしい限りですが、実を言うと本来のプログラムは、ひとつの関数だったのです。(←こちらの方が、はるかに分かり易いプログラムでした)
それを、あえて高速化するために、分割しちゃったんです。
(もちろん、手作業ではなくコード出力プログラムは作成しました)

自分でも、「何だか変なことしているなぁ」なんて思っていたんですが・・・
(第三者からすると、バカみたい・・・ですよね)

具体的には、オセロの石の反転関数と(指定の位置に)着手できるかを判定する関数の2つの処理を64分割したのです。
ですから、正確に言うと64処理×2=128個の関数を作ってしまいました。
#なんとコレで、オセロプログラムソース全体の2/3を使ってしまいました。

それでも、その分割することで、約10%程度のスピードアップになったので、「まぁいっか!」と言う気持ちと「やりすぎちゃった!」という気持ちとが半々です。

しかし、これだけやっても所詮は10%程度しか改善できていないのは、別の処理に問題があるんだろうと考えております。
#探索処理に置換表を使うとか、枝刈の方法等など・・

そんな訳で、「高速化」にムキになってしまっていた私だったのです。

改善する(改悪?)する度に一定の効果はあるのですが、ますます、プログラムコードが分かりずらくなってしまっています。

非常に参考になりました。ありがとうございました。

PS
拙作オセロ(リバーシ)ソフトです。

http://homepage3.nifty.com/ae85fcmxs/02 ... versi.html

処理速度が遅いわりには、「弱い」のです。これを何とかしたくって、もがいている状態なのです。


通報する
ページトップ
   
 記事の件名:
投稿記事Posted: 2009年8月11日(火) 21:02 
オフライン

登録日時: 2005年5月31日(火) 10:52
記事: 264
お住まい: 高知
オセロですか。

なかなか面白そうなことをしているんですね。

オセロのアルゴリズムの研究でもしない限り、速度はあんまり気にしなくても
良い気がしますが、ゲームだとサクサク感も重要だったりしますよね。


あまり、役に立たないと思いますが、
こんな方法もあると言うことだけご紹介しておきます。

Select Case文を使用して関数を呼び出す方法は線形探索法という
探索アルゴリズムと同等の構造をしていて、
呼び出されている関数に偏りがあった場合、
条件判断の回数が増減しますので
全体の計算速度がかなり遅くなったり、逆に速くなったりします。

一方、takさんが紹介されたプログラムはハッシュ法と呼ばれる
探索アルゴリズムを応用した、関数の呼び出し方です。
この場合、呼び出そうとする関数を一発で配列から取り出せるので、
最も高速な方法だと言えます。
ただし、配列を予め用意しないといけませんのでプログラムが大きくなります。

これを踏まえて、私の作ったプログラムを見てください。 これは特殊な条件がそろわないと使えない分岐方法ですが、
今回のように0~63の間で分岐する場合、
どの数値を入力しても、条件判断回数が6回となり、
安定して使えます。


一般にアルゴリズムは時間と空間のトレードオフといわれています。

SelectCaseを使う方法では速度が遅い分、リソースの量は少なくてすみます。
配列と関数ポインタの場合は、速度が速い分、配列という形で
メモリーのリソースを余分に消費している訳です。


プログラムはほんの少しの工夫で速くなったり、プログラムを小さくできるので
奥が深いですね。
アルゴリズムも書籍でいろいろと紹介されているので、
一読してみると面白いと思いますよ。


通報する
ページトップ
 記事の件名:
投稿記事Posted: 2009年8月11日(火) 21:45 
コード拝見させていただきました。すごいですね!

6ビットのドコが1であるのかによって、そのビット分を加算していくという事ですよね?だから6回の条件分岐で済むと・・・
(すみません。パっと見た感じでそう判断してしまっています。良く熟読(?)していないので、間違って解釈しているかもしれません。後でジックリ見させてもらいます)

アルゴリズムの奥深さは確かに感じています。
プログラムを夢中で作成していたのは20年以上前の事でして、最近になってオセロソフトを作り直しているのですが、「どう作って良いのか」と思案する事が多いです。

>アルゴリズムも書籍でいろいろと紹介されているので、一読してみると面白いと思いますよ。

そうですね。私は実際に本を買って勉強した事ないんです。
(アルゴリズム系のものです。リファレンス的マニュアルは購入した事はありますが・・・)
「慣れるより慣れろ」だ!なんて思っていた時期がありましてね。
確かにそれも、そうなのかもしれませんが、アルゴリズムに関しては「自力で考える」のも限界はありますね。
#もちろん、自力で考えた場合の方がスキルアップにはなると思います

とても参考になりました。ありがとうございました。


通報する
ページトップ
   
期間内表示:  ソート  
新しいトピックを投稿する  トピックへ返信する  [ 5 件の記事 ] 

全ての表示時間は UTC+09:00 です


オンラインデータ

このフォーラムを閲覧中のユーザー: Ahrefs [Bot] & ゲスト[22人]


トピック投稿:  可
返信投稿:  可
記事編集: 不可
記事削除: 不可
ファイル添付: 不可

検索:
ページ移動:  
Powered by phpBB® Forum Software © phpBB Limited
Japanese translation principally by ocean