double型の変数の正負の判定
■ このスレッドは過去ログ倉庫に格納されています
0001Jun
NGNGこちらの方がふさわしいと思いまして、こちらに書かせて
頂きました。すみません。
私は、時系列検索の高速化について研究しているものです。
ある手法を実装する上で、double型の変数aの正負の判定
(実は2直線の交差判定)をしたいのですが
if(a > 0.0)
でやると、遅いのです。で、正負の判定をビット演算等の
高速演算でやりたいのですが、詳しい方教えて頂けないで
しょうか?それと、もし、
y = a x + b
y = c x + d
という2直線があるときにそれが区間[p..q]の間で交差する
かどうかを高速に判定するアルゴリズムをご存知の方がいら
っしゃったらお教えいただけないでしょうか? 厚かましいお
願いで本当に申し訳ありません。
0002名無しさん＠お腹いっぱい。
NGNGif( a < 0.0 ) ＝ if( a >> 31 ) // 符号ビットで判定する
# 遅い原因はこれじゃないと思うが．．．
0003名無しさん＠お腹いっぱい。
NGNG２直線をそれぞれFa、Fbと置いて、
if(Fa(p) < Fb(p)){
if(!(Fa(q) < Fb(q))){
return true;
}
}else{
if(!(Fa(q) > Fb(q))){
return true;
}
}
ってこれで遅いっていうのかな？
ってゆうかこのアルゴリズム駄目？大丈夫？
よくわからんので検証お願いします。
その前に高速じゃない？
0004Jun
NGNGこの方は、
{(a * p + b) - (c * p + d )} * {(a * q + b) - (c * q + d)}の正負を判定
するのと同意ですよねえ。これでは＠｀ doubleの掛け算が5回と最後にそれの正
負を判定するif文がありますので＠｀ 遅いと言えます。ビット演算で何とかなら
ないかと思いまして。 どうもありがとうございます。
0005ああっ名無しさまっ
NGNG0006Jun
NGNGdouble型に>>をすると
invalid operands to binary >>
と怒られてしまうのです。
0007名無しさん＠お腹いっぱい。
NGNG0008名無しさん＠お腹いっぱい。
NGNGもっと細かく条件を出さないと最速の処理はわかんないよ
例えば、
a＠｀b＠｀c＠｀dよりp＠｀qの頻度が高いケースまたは
a＠｀cとb＠｀dで頻度が異なるケースにおいて高速：
x=(d-b)/(a-c)を求めてp≦x≦qであるなら交差
とか。
0009名無しさん＠お腹いっぱい。
NGNG00108
NGNG0011Jun
NGNGところで、f ((char)a >> 3)はうまくいきませんでした。
8さん。その方法だと、交差判定にif文が2回必要になって
しまいます。私のプログラムでは交差判定が数億回行なわ
れます。ですから、極力この部分を速くしたいのです。
なお、a＠｀cとb＠｀dで頻度は全く同じです。
0012名無しさん＠お腹いっぱい。
NGNG0013名無しさん＠お腹いっぱい。
NGNGま、正負判定を0 >以外でってんなら、
typedef union {
int i;
double d;
} val_t;
val_t v;
v.d = hoge;
if (v.i & 0x80000000) { // IEEE
// minus
} else {
// plus
}
なんてのは出来るが。
シフト命令とAND命令とどっちが速いかはアーキテクチャ依存だけど、
最近はシフトの方が速いかなあ。ともかく、CPUとOS位書かないとダメよ。
0014名無しさん＠お腹いっぱい。
NGNGac := a - c;
bd := b - d;
で
(p * ac + bd) * (q * ac + bd)
だと、乗算3回かも
00158
NGNGIFとどちらが速いかな？
00168
NGNG((var_t)(x-p).i|(var_t)(q-x).i)& 0x80000000
なんか合体スレになってきたな
でも普通は>>14-15が速いと思うよ
実数計算した結果が汎用レジスタに格納されるって
アーキテクチャなら話は違ってくるけど
0017Jun
NGNGスペックはSUN Ultra Enterprise 450 running Solaris 2.6 です。
> >>4を焼きなおして (x-p)*(q-x) が正負で判定できるけど、
すyes みません。これ＠｀ 理解できません。説明してもらえないでしょ
うか?
>13さん
なるほど。そうやるわけですか。これで怒られずに済みそうですね。
これでif文を完全に取ってしまえばかなり高速化できそうですね。
皆様ありがとうございます。おかげさまで、符号を取り出す方法が
分かりました。これからif文を使わずにやる方法を考えてみます。
00188
NGNGq-xは、x≦qの時0以上となる
p<qが保証される環境では、両方が0未満となるケースはない
よって(x-p)*(q-x)が0以上となれば、p≦x≦qが満たされたことになる
001913
NGNGあー。それはいいんだけど、プロファイラーはすでに試しましたか？
行単位での実行時間の集計とって、高速化すべき場所を特定できます。
SUN + Solarisなら最初っからついてるはず。
0020ああっ名無しさまっ
NGNG「if文を使わずにやる方法」とか言ってるけど、
・どういうコードにコンパイルされてるか
・ターゲットではどのようなコードの実行効率が高いか
ちゃんと把握してる？
a が float とかなら別だけど、if(a > 0.0) がそんなに重いとも思えないんだけど。
0021Jun
NGNGわかりました。ありがとうございます。
>19さん
ありがとうございます。プロファイルやってみました。確かにループ
の部分が殆どの時間をしめているのがわかりました。ただ、おっしゃ
っておられる行単位のプロファイルの場合のgprofのオプションが
manを調べたのですが、わかりませんでした。申し訳無いのですが
お教え頂けないでしょうか？
>20さん
floatが遅い原因というのは、一度doubleにキャストしてから比較
するからなのでしょうか？ floatが別というのは、どうしてですか？
実は、if文を使うとそれまでCPUが先読みしていたコードを全部棄てて
しまうからifは遅いというのを聞いたことがありまして、それを信じて
いたのですが、まちがっているでしょうか？
0022名無しさん＠お腹いっぱい。
NGNGま、そういう処理系も残ってるだろうね。
＞コードを全部棄てて
最近のコンパイラの最適化は、分岐する場合としない場合と
両方先読みするんじゃないのかな？
80386のプリフェッチキューとかの話かしら？
0023名無しさん＠お腹いっぱい。
NGNGfloat -> double の変換が行われる。また、昔のコンパイラでは float は
常に double に変換されてから演算されていたので、一般に float は重
かった。今時のコンパイラならもうちょっと気を利かせて効率のよいコード
を生成してくれるかも知れん。
0024名無しさん＠お腹いっぱい。
NGNG>しまうからifは遅いというのを聞いたことがありまして、それを信じて
>いたのですが、まちがっているでしょうか？
if 文に限らず、分岐が発生すればプロセッサのパイプラインの内容が破棄されて
遅延が生ずるのは良くあることだけど、問題の原因と対策をプログラマが正しく
理解していなければ最適化についてのトレードオフは判断できない筈だから、生
半可な知識で最適化云々と言うのは方法として間違い。プロファイラを使うとか、
コンパイラの出力コードを吟味する等の作業が最も確実で効率的。
0025名無しさん＠お腹いっぱい。
NGNG>>13-14さんを組み合わせると
UP.d=(p * ac + bd) ;
UQ.d=(q * ac + bd) ;
(UP.i ^ UQ.i) & 0x80000000
で出来る。掛け算２回と割り算１回のどちらが早いかの比較だね
002625
NGNGcount += (((UP.i ^ UQ.i) & 0x80000000 )-1 &1);
みたいな方法も考えられる。
ビット位置を合わせる方法は、論理は反対になるけど
(unsigned)して シフトするのが早ければそうすればいい。
というか論理が反対になったら結果の totalから total-countと
引けばいいだけ。
■ このスレッドは過去ログ倉庫に格納されています