9

実行パスで何度もヒットするバイナリ検索ループがあります。

プロファイラーは、検索の分割部分（検索範囲の高いインデックスと低いインデックスを指定して中間のインデックスを見つける）が、実際には検索の最もコストのかかる部分であり、約4倍であることを示しています。

（私は思う）効率的な二分探索では、正確な中間値を見つけることは重要ではなく、どちらの方向にもバイアスがない中央付近の値だけを見つけることが重要です。

mid = (low + high) / 2はるかに高速なものに置き換えるためのビットをいじるアルゴリズムはありますか？

編集：言語はC＃ですが、同等のビット演算はどの言語でも有効です（ただし、パフォーマンス上の利点はない場合があります）。そのため、C＃タグをオフのままにしました。

4

6 に答える 6

19

これは、オーバーフローの問題に悩まされていない平均のビットハックバージョンです。

unsigned int average (unsigned int x, unsigned int y)
{
  return (x&y)+((x^y)>>1);
}
于 2009-06-20T01:47:15.617 に答える
12 
int mid = (low + high) >>> 1;

整数のオーバーフローが問題になる場合、中点の計算に「（低+高）/2」を使用すると正しく機能しないことに注意してください。

于 2009-06-19T21:52:42.890 に答える
7

ビットシフトを使用して、オーバーフローの問題を克服することもできます。

low + ((high-low) >> 1)

ただし、最近のコンパイラとインタプリタはビットシフトとして2による除算（または他の2の定数乗による除算）を行うことを期待していることを認めなければならないので、それが本当に役立つかどうかはわかりません-試してみてください。

于 2009-06-19T22:40:33.497 に答える
5

ニルスの答えをさらに拡張するために、リチャード・シュロッペルがこれを発明しました。

http://www.inwap.com/pdp10/hbaker/hakmem/boolean.html#item23

アイテム23（シュロエッペル）：

（A AND B）+（A OR B）= A + B =（A XOR B）+ 2（A AND B）。

(A + B)/2 = ((A XOR B) + 2(A AND B))/2
          =  (A XOR B)/2  + (A AND B)
          =  (A XOR B)>>1 + (A AND B)


avg(x,y){return((x^y)>>1)+(x&y);}

(A AND B) + (A OR B) = A + BなぜならA AND B、2の共有（AとBの間）の累乗の合計を与えるので、共有さA OR Bれるものと共有されないものの両方を与えるので、次のようになります。

(A AND B) + (A OR B) = 
   (sum of shared powers of two) + 
   ((sum of shared powers of two) + (sum of unshared powers of two)) = 
     (sum of shared powers of two) + 
     ((sum of shared powers of two) + (sum of powers of two of A only) + 
     (sum of powers of two of B only)) = 
       ((sum of shared powers of two) + (sum of powers of two of A only)) + 
       ((sum of shared powers of two) + (sum of powers of two of B only)) 
= A + B.

A XOR BAとBの間で異なるビットのマップを提供します。したがって、

A XOR B = (sum of powers of two of A only) + (sum of powers of two of B only).

したがって：

2(A AND B) + (A XOR B) = 
       ((sum of shared powers of two) + (sum of powers of two of A only)) + 
       ((sum of shared powers of two) + (sum of powers of two of B only)) 
= A + B.
于 2012-05-06T11:43:20.790 に答える
0

正しく思い出せば、配列の真ん中を使用すると実際には遅くなる場合があります。解決策は、配列を二等分するインデックスの選択をランダム化することです。配列の中央値を決定するためのアルゴリズムについても同様に当てはまります。

正確な詳細は思い出せませんが、iTunesのMITアルゴリズムシリーズの講義6で聞いたことを覚えています。

于 2009-06-20T01:16:19.860 に答える
0

低+（（高-低）/ 2））を試してください。これは、2つの数値の平均のみを取得しているため、機能するはずです。これにより、バイナリ検索リストがかなり大きい場合にアルゴリズムにかかる時間が短縮されます。これは、high-lowがhigh+lowよりもはるかに小さいためです。

于 2015-07-15T18:24:19.860 に答える