HSPTV!掲示板

スレッド一覧 | 新規書き込み | 新着一覧 | 使い方 | 過去ログ

未解決

解決

停止

削除要請


	2012 0905	てん	条件分岐と処理速度について	12

てん

2012/9/5(Wed) 02:02:16|NO.49136

■はじめに

はじめて「ひとりごと」というカテゴリを使います。
今回、ある変数の値で60パターンに条件分岐するプログラムを書くことになりました。
処理速度の問題から、最適なパターンは何なのか考える必要が出てきました。

私が思いついたのは以下の3通りの方法です。
①単純にif文を連ねる



	if a=0 { DoSomething() }
	if a=1 { DoSomething() }
	if a=2 { DoSomething() }
	if a=3 { DoSomething() }
	…

②条件に当てはまらなかったときのみ、以降の条件を行う。



	if a=0 { DoSomething() 
	} else : if a=1 { DoSomething() 
	} else : if a=2 { DoSomething() 
	} else : if a=3 { DoSomething()
	…

③条件に当てはまった時点で判定を終了する。



	if a=0 { DoSomething() : goto *last }
	if a=1 { DoSomething() : goto *last }
	if a=2 { DoSomething() : goto *last }
	if a=3 { DoSomething() : goto *last }
	…

なお、switchマクロは展開後の形から、③のパターンに相当します。

さて、普通に考えて①が最も遅いことはわかります。
例えばa=0の場合、2行目以降は無駄な評価になってしまうからです。
②と③ではelseを処理する負荷がない分、僅差で③が勝つと予想されました。

そこで、以上のことを確認してみました。

この記事に返信する

てん

2012/9/5(Wed) 02:02:37|NO.49137

■実験

テスト方法は以下のとおりです。
・分岐は a=0 ～ a=99 の計100パターン用意。
・分岐の中身は何も記述していない。
・分岐を10万回繰り返す。
・処理の総時間をスコアとする。

テストケースは3通り用意しました。
a) aが完全ランダム(0～99)
b) a=0で固定
c) a=99で固定
なお、(a)に関しては、乱数のパターンを全てのテストで統一しました。
（randomizeの初期化パラメータを指定しました）

テストスクリプトは以下のとおりです。




	#define TEST_EQUATION rnd(99)	//Select Test Case
	
	//Test Start
	t_start = (gettime(5)*60+gettime(6))*1000+gettime(7)
	repeat 100000
		gosub *test1
	loop
	t_end = (gettime(5)*60+gettime(6))*1000+gettime(7)
	
	//Result
	dialog (t_end - t_start)
	end
	
	*test1	//タイプ①
		a = TEST_EQUATION
		
		if a=0 {}
		if a=1 {}
		if a=2 {}
		if a=3 {}
	
		…	
	
		if a=98 {}
		if a=99 {}
	
	return

てん

2012/9/5(Wed) 02:02:55|NO.49138

■結果と考察

テストは各ケース、各アルゴリズムについて3回ずつ行いました。
結果は以下のとおりです。(単位:ms）



	a) aがランダム
	①	3129	3067	3038
	②	1614	1556	1681
	③	1602	1579	1581

	b) a=0で固定
	①	3050	3174	2919
	②	 103	 126	  94
	③	 106	 111	 100

	c) a=99で固定
	①	2972	2846	2865
	②	2891	2921	2925
	③	3128	3046	2983

最後に、全スコアを合計して、各アルゴリズムの平均所要時間を求めました。
	d) 平均所要時間
	①	3006
	②	1545
	③	1581

やはり、無駄な評価の少ない②、③が①よりも高スコアとなりました。
特に、b)のテストケースの場合、①は評価回数が99回であるのに対し、
②③は1回だけで済むというメリットは大きかったようです。

一方全てのアルゴリズムで99回評価が必要なc)のケースでは
どのようなアルゴリズムを用いてもあまり差が出ないことがわかりました。

最終結果d)では予想に反して、②が③を僅差で上回る結果となりましたが、
所要時間の1/40程度の差ですので、現実の処理に於いては誤差の範囲として構わないと思います。

てん

2012/9/5(Wed) 02:03:50|NO.49139

■最後に
今回はスコアの上では②が最良なアルゴリズムという結果になりましたが、
実装の容易さや可読性などを考慮すると③の方法を取るのが最善であると思われます。
（switch文は基本的に③と同様の構造ですので、実際にはswitch文を使うのが最善？）

switch文のマクロと言えば、マクロ展開後に生成される_switch_swとはどのような働きを持つのでしょうか。
この文章を書くに当たりいろいろ検証したのですが、わからずじまいでした。
何方か御存知のかたいらっしゃいましたらお教えいただけたらと思います。

HSPではswitchをifに置き換えることで擬似的にswitch～case構文を構成していますが
言語仕様として元からswitch構文を備えている言語の場合、
「評価値をもとにジャンプするラベルを決定しジャンプする」というアルゴリズムのものが大半のようです。
ラベルの決定には、評価値をもとに一意な値を得る計算式のようなものがあるっぽいです。
なるほど、これなら評価を一切含みませんなぁ。

この仕様は、コンパイラの仕様がどうこう、という話ですので、どうしようもないものと思われます。
もしどなたか「マクロなどで実装可能だ！」という方いましたらご報告ください。

だらだらと書いてきましたが、結論としては



HSPにおいて多分岐構造を記述するにはswitch構文が最適である。

という話でした。
駄文にお付き合いいただきありがとうございました。

2012/9/5(Wed) 05:32:10|NO.49143



repeat a
if a!cnt : continue
b=cnt
break
loop
goto *b

適当に書いただけですが、たしか変数をラベルに使えたような気がします。
最初に飛び先を定義した配列を作っておいて、cntで選択する等。

2012/9/5(Wed) 05:45:17|NO.49144

c=a\2
if c=0 goto *GUUSUU
goto *KISUU
*KISUU
if a=1........
.....

*GUUSUU
if a=0........
.....

としても効率的かと。

y.tack

2012/9/5(Wed) 11:11:09|NO.49148



do
	if a=0 { 
		DoSomething()
		_break	
		}
	if a=1 { 
		DoSomething()
		_break	
		}
	if a=2 { 
		DoSomething()
		_break	
		}
	if a=3 { 
		DoSomething()
		_break	
		}
until 0

こういう書き方もありますよ
goto使うかもしれないみたいなので
repeatは使わないかな？僕の場合

後、60くらい分岐するみたいなんですけど
全部いっぺんに処理せず




	do
	if a<10 { 
		DoSomething_A()
		_break	
		}
	if a<20 { 
		DoSomething_B()
		_break	
		}
	if a<30 { 
		DoSomething_C()
		_break	
		}
	if a<40 { 
		DoSomething_D()
		_break	
		}
	until 0

のようにいくつかにまとめた方がいいと思います

てん

2012/9/5(Wed) 19:00:02|NO.49154

ご指摘ありがとうございます。
確かに私の考えのように１つずつ評価していく方式（以下、直列評価）よりも
大まかな評価から少しずつ絞っていく方式（以下、並列評価）のほうが速度は指数関数的に
早くなりますね。なぜ思いつかなった、自分・・・

ただ、実際にはケースに相当な偏りがある場合、
並列評価法では冗長な評価をしてしまう可能性もあります。
（a=0 or 99で固定した場合など）

偏りがなく、等確率で出ると思われるケースには並列評価を、
偏りがあり、出やすいデータについては直列評価を用いると良いのかもしれません。

例えば、aの値が 0 > 1 > 2=3=4=5=6=7=8=9　の順に出やすいことがわかっている場合



if a=0 { DoSomething() : goto *last }			//a=0
if a=1 { DoSomething() : goto *last }			//a=1
if a>5 { 
	if a>7 {
		if a=9 { DoSomething() : goto *last }	//a=9
		DoSomething() : goto *last		//a=8
	}
	if a=7 { DoSomething() : goto *last }		//a=7
	DoSomething() : goto *last			//a=6
}
if a>3 {
	if a=5 { DoSomething() : goto *last }		//a=5
	DoSomething() : goto *last			//a=4
}
if a=4 { DoSomething() : goto *last }			//a=3
DoSomething() : goto *last				//a=2

*last
return

とすれば早くなる・・・のかな？
データがどの程度偏っているのかにもよるので検証はなかなか難しそう。。。

てん

2012/9/5(Wed) 19:10:38|NO.49155

そしてラベルを変数に入れられるというもの、初耳でした。

それ使えば本物のswitch構文のように一発ジャンプ可能じゃん！とか思ったのですが、
60パターンもあると準備に一苦労ですね…

ケースの値から、ハッシュ値を生成して、
配列変数にハッシュ値をインデックスにしてラベルを突っ込む。
実際にswitch構文の所へ来たら評価値を元にハッシュ値を生成、ジャンプするラベルを決定する

とか考えたのですが、
①衝突なくハッシュ値を作る方法が不明。配列のインデックスなので0～にしないといけない。
まぁ0スタートじゃなくてもいいんですけど、とりあえず現実的な値にしないといけない。

②ジャンプ先のラベル一覧が入った配列を予め準備しなくてはならない。

の2点が問題ですね。。。難しい。。。

てん

2012/9/5(Wed) 19:15:23|NO.49156

まぁ今回この問題を考えるきっかけが

テキストエディットコントロールを自作する際に
onkey命令でジャンプした先で、押されたキーを判定する

というものでした。キーコードは0～255なので
とりあえずはキーコードをインデックスにしたラベル配列を用いる形で行こうかと思います。

@key

2012/9/5(Wed) 19:41:20|NO.49157

全部で約15時間も実行したんですか・・・
自分も今60個以上使うケースになっているのでありがたいです

y.tack

2012/9/5(Wed) 20:26:28|NO.49161

なんか個別に分岐する前に大雑把に分岐した方が管理しやすいし見やすいと思ってたんですけど
＞テストスクリプトは以下のとおりです。
99まで順に分岐を書いたんですね^^
やってること的にも全部似たような処理なんですね

＞とりあえずはキーコードをインデックスにしたラベル配列を用いる形で行こうかと思います。
結局はif a==xのxをカウンタにして繰り返しで処理した方が良さそうですね
分岐処理はそんなに重くないと思うんで見易さ第一だと思います

＞テキストエディットコントロールを自作する際
それをあえてやり遂げようとする気力に感服です

GOOD LUCK!

2012/9/6(Thu) 00:04:37|NO.49165

でも結局は下手に小技を使うよりも、べたな書き方の方が
後々便利だったりする。