HSPポータル
サイトマップ お問い合わせ


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構文が最適である。
という話でした。
駄文にお付き合いいただきありがとうございました。



KA

リンク

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


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

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



KA

リンク

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

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

ただ、実際にはケースに相当な偏りがある場合、
並列評価法では冗長な評価をしてしまう可能性もあります。
(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!



KA

リンク

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

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



ONION software Copyright 1997-2018(c) All rights reserved.