2

ウィキペディアの記事には、次のように「最適化された」バージョンのバイナリ検索を提示するBinary Searchというセクションがあります。Deferred detection of equality

int binary_search(int A[], int key, int imin, int imax)  
{  
  while (imax > imin)  
  {  
    int imid = (imin + imax) / 2;  
    if (A[imid] < key)  
      imin = imid + 1;  
    else  
      imax = imid;  
  }  
  if((imax == imin) && (A[imin] == key))  
    return imin;  
  else  
    return KEY_NOT_FOUND;  
}

Is this .... algorithm uses only one conditional branch per iteration
true? つまり、if命令は翻訳されCMP、命令はアセンブリに翻訳されているので、言語よりも言語の方が優れているとはBranch思えません 。高水準言語で考慮する必要があるような違いはありますか? 「deffered」バージョンのコードは管理者にとってよりタイトに見えますが、ステートメントの作成方法に最適化やペナルティはありますか?if-elseif-else if-else
if-else

4

1 に答える 1

3

重要な概念は、反復ごとに1つ少ない条件を使用することです。つまり、等価性チェックはwhileループの外側に移動されたため、1回だけ実行されますが、基本バージョンでは毎回チェックする必要があります¹。

とはいえ、最適化されたフォームを使用したときに実際に測定可能な違いがあるかどうかはわかりません。たとえば、次のことを考慮してください。

  1. 比較しているのが2つの整数だけの場合、コンパイラーは、比較結果を1回だけ計算できることを検出して、どの分岐を取得するかを評価できます。
  2. 二分探索はO（logN）であるため、検索する要素の数が非常に多い場合でも、実行される反復回数は実際には非常に少なくなります。違いが見られるかどうかは議論の余地があります。
  3. 投機的実行や分岐予測などの最新のCPU機能の実装（特にバイナリ検索のような「優れた」アルゴリズム）は、この最適化よりも目に見える効果をもたらす可能性があります（ただし、私のリーグ外です）。

ノート：

¹実際には、同等性の比較が終了したときにチェックする必要のない別の条件ですが、概念的には違いはありません。

于 2012-04-25T15:45:57.183 に答える