Fortran中二分查找算法的效率与线性查找算法的效率比较

Question

Fortran中二分查找算法的效率与线性查找算法的效率比较

performancefortranbinary-searchfortran77linear-search

9

这个问题涉及在相邻的存储中针对预排序数组进行线性搜索和二进制搜索的效率比较。

我有一个用Fortran（77！）编写的应用程序。我的代码部分经常需要在数组中查找索引，使得gx（i）<= xin <gx（i + 1）。我目前实现了这个功能为二进制搜索 - 抱歉，使用Fortran 90时语句标签和goto会略有不同...

        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个元素大小的数组...

- mgilson

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- usr · Accepted Answer

对于小数组而言，问题不在缓存上。你是正确的：小数组很可能会很快地被缓存起来。

问题在于二分查找中分支预测容易失败，因为分支随机地以数据相关的方式被选择或跳过。分支预测失误会导致CPU流水线停滞。

这种效应非常严重。你可以轻松地线性搜索3到8个元素，所需的时间与执行一次二分查找分支相同（而你需要执行多次二分查找分支）。确切的分界点需要进行测量。

使CPU流水线停滞非常昂贵。一个Core i7每个时钟周期最多可以执行4条指令（在3 GHz时可达到12亿条指令每秒！），但这仅限于没有停滞的情况。

有些无分支算法使用条件移动CPU指令来执行二分查找。这些算法基本上展开了32个搜索步骤，并在每个步骤中使用一个CMOV（32步是理论上的最大值）。它们是无分支的，但不是无停滞的：每个下一步都完全依赖于前一个步骤，因此CPU不能在指令流中快速执行，必须一直等待。因此，它们并不能解决这个问题，只能稍微改善一下。