9

この質問は、線形検索の効率と、連続したストレージ内の事前に並べ替えられた配列のバイナリ検索の効率に関するものです...

Fortran (77!) で書かれたアプリケーションがあります。コードの一部で頻繁に行われる操作の 1 つは、配列内のインデックスを検索することgx(i) <= xin < gx(i+1)です。私は現在、これを次のように実装していますbinary search-- ステートメントのラベルについては申し訳ありませんが、- gotofortran 90 を使用すると、同等のステートメントがどのようなものになるかをコメントしました...

        i=1
        ih=nx/2
201     continue  !do while (.true.)
           if((xin.le.gx(i)).and.(xin.gt.gx(i+1)))then  !found what we want
              ilow=i+1; ihigh=i
              s1=(gx(ihigh)-xin)/(gx(ihigh)-gx(ilow))
              s2=1.0-s1
              return
           endif
           if(i.ge.ih)then
              goto 202 !exit
           endif
           if(xin.le.(gx(ih))then !xin is in second half of array
              i=ih
              ih=nx-(nx-ih)/2
           else !xin is in first half of array
              i=i+1
              ih=i+(ih-i)/2
           endif
        goto 201  !enddo

しかし、今日、ウィキペディアで二分探索について読んでいて、これに出くわしました。

Binary search can interact poorly with the memory hierarchy 
(i.e. caching), because of its random-access nature. For 
in-memory searching, if the span to be searched is small, a
linear search may have superior performance simply because 
it exhibits better locality of reference.

私はこのステートメントを完全には理解していません.キャッシュフェッチは一度に大きな（っぽい）チャンクに集められたので、配列の先頭から開始すると、配列のほとんどがキャッシュにあると思いました.すでに（少なくとも線形検索の場合と同じくらい）、それが問題になるとは思いませんでした。

だから私の質問は、どちらのアルゴリズムがより優れたパフォーマンスを発揮するかを知る方法はありますか (線形検索またはバイナリ検索ですか?) 配列サイズの境界はありますか? 私は現在、約100要素のサイズの配列を使用しています...

4

1 に答える 1

13

小さな配列の場合、問題はキャッシュではありません。その通りです。小さな配列はすぐにキャッシュされる可能性があります。

問題は、分岐がデータに依存する方法でランダムに取得またはスキップされるため、二分探索では分岐予測が失敗する可能性が高いことです。分岐予測ミスは、CPU パイプラインをストールさせます。

この影響は深刻な場合があります。単一のバイナリ検索分岐を実行するのにかかる時間と同じ時間で、3 ～ 8 個の要素を直線的に簡単に検索できます (また、複数のバイナリ検索分岐を実行する必要があります)。正確な損益分岐点を測定する必要があります。

CPU パイプラインのストールは非常にコストがかかります。Core i7 は、1 クロック サイクルあたり最大 4 つの命令をリタイアできます (3 GHz で 1 秒あたり 12 ギガ命令!)。ただし、失速していない場合に限ります。

条件付き移動 CPU 命令を使用してバイナリ検索を実行するブランチフリー アルゴリズムがあります。これらのアルゴリズムは、基本的に 32 の検索ステップをアンロールしCMOV、各ステップで a を使用します (32 ステップが理論上の最大値です)。それらは分岐フリーですが、ストール フリーではありません。次の各ステップは前のステップに 100% 依存するため、CPU は命令ストリームで先にチャージできません。ずっと待たなければなりません。したがって、彼らはこの問題を解決するのではなく、わずかに改善するだけです。

于 2012-05-09T21:15:07.723 に答える