fortran中的二元搜索效率与线性搜索效率

Question

这个问题是关于线性搜索的效率与连续存储中预排序数组的二进制搜索的效率...

我有一个用fortran编写的应用程序(77!).我的部分代码的一个常见操作是在数组中找到索引gx(i) <= xin < gx(i+1).我目前已经实现了这个binary search- 对于声明标签而言goto- 并且- 我已经评论了使用fortran 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.

我不完全理解这个陈述 - 我的印象是缓存提取一次收集在大(ish)块中,所以如果我们从数组的开头开始,我认为大多数数组都在缓存中已经(至少与线性搜索一样多),所以我认为这不重要.

所以我的问题是,有什么方法可以判断哪种算法会表现得更好(线性搜索还是二进制搜索？)是否存在数组大小边界？我目前正在使用大约100个元素的数组...

Answer 1

对于小型阵列,问题不在于缓存.你是对的:一个小阵列可能很快被缓存.

问题在于分支预测可能因二进制搜索而失败,因为以数据相关的方式随机获取或跳过分支.分支预测错失了CPU流水线.

这种影响可能很严重.您可以在执行单个二进制搜索分支所需的同一时间内轻松地线性搜索3到8个元素(并且您需要执行多个二进制搜索分支).需要测量精确的收支平衡点.

停止CPU管道非常昂贵.Core i7每个时钟周期最多可以退出4条指令(3 GHz时每秒12千兆指令!).但只是,如果你不拖延.

有一些无分支算法通过使用条件移动CPU指令进行二进制搜索.这些算法基本上展开了32个搜索步骤,并CMOV在每个步骤中使用a (32个步骤是理论最大值).它们是无分支但不是无失速:每个下一步都取决于前一个步骤100%,因此CPU无法在指令流中向前充电.它必须一直等待.所以他们没有解决这个问题,只是略有改进.