9

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

我有一个用 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

但是，今天，我在 Wikipedia 上阅读有关二分搜索的内容时遇到了这个问题：

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

4

1 回答 1

13

对于小型阵列，问题不在于缓存。你是对的：一个小数组很可能被快速缓存。

问题是分支预测对于二分搜索很可能会失败，因为分支是以数据相关的方式随机选取或跳过的。分支预测未命中会使 CPU 流水线停滞。

这种影响可能很严重。您可以在执行单个二进制搜索分支（并且您需要执行多个二进制搜索分支）的同时轻松地线性搜索 3 到 8 个元素。需要测量准确的盈亏平衡点。

停止 CPU 流水线非常昂贵。Core i7 每个时钟周期最多可以退出 4 条指令（3 GHz 时每秒 12 条千兆指令！）。但只有在你不拖延的情况下。

有无分支算法通过使用条件移动 CPU 指令进行二进制搜索。这些算法基本上展开 32 个搜索步骤并CMOV在每个步骤中使用 a（32 个步骤是理论上的最大值）。它们是无分支的，但不是无停顿的：每个下一步都 100% 依赖于前一步，因此 CPU 无法在指令流中提前充电。它必须一直等待。所以他们没有解决这个问题，只是稍微改进一下。

于 2012-05-09T21:15:07.723 回答