48

数値の絶対値を返す演算を実装する最速の方法はどれですか?

x=root(x²)

また

if !isPositive(x):
    x=x*(-1)

実際、この質問は、どのくらい速いかif(そしてなぜお願いしますか) として翻訳できます。

私の大学のプログラミングの教授は、s は非常に遅いので避けるようにいつも私に言いましたifが、どのくらい遅いのか、そしてその理由をいつも聞くのを忘れていました。ここに誰か知っていますか？

4

15 に答える 15

88

if ステートメントを使用せずに 2 の補数の整数の絶対値を計算するための優れたトリックがあります。理論的には、値が負の場合はビットを切り替えて 1 を追加する必要があり、それ以外の場合はビットをそのまま渡します。XOR 1 はたまたま A をトグルし、XOR 0 はたまたま A をそのまま残します。だからあなたはこのようなことをしたい：

  uint32_t temp = value >> 31;     // make a mask of the sign bit
  value ^= temp;                   // toggle the bits if value is negative
  value += temp & 1;               // add one if value was negative

原則として、わずか 3 つのアセンブリ インストラクション (分岐なし) で実行できます。そして、math.h で得られる abs() 関数がそれを最適に行うと考えたいと思います。

分岐なし == パフォーマンスの向上。上記の @paxdiablo の応答とは対照的に、これは、コード内の分岐が多いほど、分岐予測子が間違ってロールバックする必要があるなどの可能性が高くなる深いパイプラインで非常に重要です。可能であれば、物事はあなたのコアで全速力で進み続けます:)。

于 2010-01-15T19:59:26.887 に答える
75

条件分岐は単純な算術演算よりも遅くなりますが、平方根を計算するようなばかげたものよりははるかに高速です。

私の組立日からの経験則:

  • 整数演算またはビット演算: 1 サイクル
  • 浮動小数点加算/減算/乗算: 4 サイクル
  • 浮動小数点 div: ~30 サイクル
  • 浮動小数点指数: ~200 サイクル
  • 浮動小数点平方根: 実装に応じて ~60 サイクル
  • 条件分岐：平均 10 サイクル、予測が良ければ改善、予測を誤った場合はさらに悪化
于 2009-03-20T03:18:31.187 に答える
20

平方根の計算は非常に遅いため、おそらく最悪のことの1つです。通常、これを行うためのライブラリ関数があります。Math.Abs​​（）のようなもの。-1を掛けることも不要です。-xを返すだけです。したがって、良い解決策は次のようになります。

(x >= 0) ? x : -x

コンパイラはおそらくこれを単一の命令に最適化します。最近のプロセッサでは、実行パイプラインが長いため、条件が非常に高くなる可能性があります。分岐の予測が誤っていて、プロセッサが間違ったコードパスから命令の実行を開始した場合は、計算を破棄する必要があります。しかし、前述のコンパイラの最適化のため、この場合は気にする必要はありません。

于 2009-03-20T03:32:06.350 に答える
7

完全を期すために、C++ で x86 システムの IEEE 浮動小数点数に対してそれを行う方法を次に示します。

*(reinterpret_cast<uint32_t*>(&foo)) &= 0xffffffff >> 1;
于 2012-07-26T16:08:51.753 に答える
4

バリアントは、通常、マシンコードレベルで条件付きジャンプ命令に変換されるため、ifほぼ確実に平方根に比べて目がくらむほど高速になります（式の評価に続いて、複雑になる可能性がありますが、この場合は単純なのでそうではありません0 未満であることを確認します)。

数値の平方根を取るのは、かなり遅くなる可能性があります (たとえば、ニュートンの方法は、マシン コード レベルで多くのステートメントを使用します)。 if

混乱の原因となる可能性が高いのはif、命令ポインターが非連続的に変更されることが常にあるという事実です。これにより、アドレスが予期せず変更されたときにパイプラインを再設定する必要があるため、命令をパイプラインにプリフェッチするプロセッサの速度が低下する可能性があります。

ただし、そのコストは、単純なチェック アンド ネゲートとは対照的に、平方根演算を実行する場合に比べてごくわずかです。

于 2009-03-20T03:19:20.857 に答える
3

モジュロ演算は、剰余を見つけるために使用されます。つまり、絶対値です。if !pos(x) then x = x*-1 であるべきなので、質問を修正しました。（欠けていませんでした）

if ステートメントの効率については心配しません。代わりに、コードの読みやすさに注目してください。効率に問題があることがわかった場合は、コードのプロファイリングに集中して、実際のボトルネックを見つけてください。

コーディング中に効率に注意を払いたい場合は、アルゴリズムの非常に複雑な部分だけを気にする必要があります。

ステートメントが非常に効率的である場合、ステートメントは式を評価し、その条件に基づいてプログラム カウンターを変更するだけです。プログラムカウンタは、次に実行する命令のアドレスを格納します。

-1 による乗算と、値が 0 より大きいかどうかのチェックの両方を、1 つのアセンブリ命令に減らすことができます。

数値の根を見つけて最初にその数値を 2 乗することは、否定を伴う if よりも間違いなく多くの操作です。

于 2009-03-20T03:17:20.270 に答える
1

平方根を実行するのにかかる時間は、条件付きを実行するのにかかる時間よりもはるかに長くなります。条件文が遅いために条件文を避けるように教えられた場合、あなたは誤った情報を与えられています。これらは、整数の加算や減算、ビットシフトなどの簡単な操作よりもかなり低速です。そのため、このような簡単な操作を行っている場合にのみ、ループの展開が役立ちます。しかし、物事の壮大な計画では、条件文は良くて速いですが、悪くて遅いわけではありません。関数を呼び出す、または平方根を計算して条件文を回避するなどの複雑なことを行うのはおかしいです。

また、（x = x * -1）の代わりに（x = 0-x）を実行しないのはなぜですか？コンパイラーはそれらを同じように最適化するかもしれませんが、とにかく2番目のものはもっと単純ではありませんか？

于 2009-03-20T03:35:00.430 に答える
1

8086アセンブリを使用していますか？;-)

                ; abs value of AX
   cwd          ; replicate the high bit into DX
   xor  ax, dx  ; take 1's complement if negative; no change if positive
   sub  ax, dx  ; AX is 2's complement if it was negative The standard
                : absolute value method works on any register but is much
                ; slower:

   or   bx, bx  ; see if number is negative
   jge  notneg  ; if it is negative...
   neg  bx      ; ...make it positive
notneg:         ; jump to here if positive

（ひどく盗まれた）

于 2009-03-20T04:23:33.260 に答える
0

8088/8086 用に C でレトロなグラフィックス プログラミングを行っていますが、呼び出しabs()に時間がかかるため、次のように置き換えました。

/* assuming 'i' is int; this WILL NOT WORK on floating point */
if (i < 0) {
    i = ~i + 1;
}

これが高速である理由は、基本的CALLにアセンブリ内の を と交換するためJNEです。メソッドを呼び出すと、いくつかのレジスタが変更され、さらにいくつかのレジスタがプッシュされ、引数がスタックにプッシュされ、プリフェッチ キューがフラッシュされます。さらに、これらのアクションは関数の最後で元に戻す必要があり、これらすべてが CPU にとって非常に高価です。

于 2016-11-21T23:08:13.740 に答える