你能以多快的速度进行线性搜索？

Question

我正在寻找优化这种线性搜索:

static int
linear (const int *arr, int n, int key)
{
        int i = 0;
        while (i < n) {
                if (arr [i] >= key)
                        break;
                ++i;
        }
        return i;
}

数组已排序,函数应返回大于或等于键的第一个元素的索引.它们的数组不大(低于200个元素),并且会为大量搜索准备一次.如果需要,可以在第n个之后将数组元素初始化为适当的数组,如果这样可以加快搜索速度.

不,不允许二进制搜索,只能进行线性搜索.

编辑:我在博客文章中总结了有关此主题的所有知识.

Answer 1

1. 告诉你的老板,你可以把它提高50%,但需要6个月,还有一些钱.
2. 等六个月.
3. 购买新硬件.

嗯,它与通过排序数组进行线性搜索一样有意义!

(更严重的是,你能给我们一些关于为什么没有二分搜索的线索吗？)

Answer 2

到目前为止,您收到了多条建议,其中大多数建议说线性搜索对排序数据没有意义,而二进制搜索将更有效地工作.这通常恰好是那些不太关心问题的人所做出的那些流行的"听起来正确"的断言之一.实际上,如果考虑到更大的图景,在适当的情况下,线性搜索可以比二分搜索更有效.

请注意,如果我们考虑对排序数组进行单个搜索查询,则二进制搜索比线性搜索更有效.对此没有任何争论.此外,当您对同一数据执行多个完全随机的查询时,二进制搜索仍然胜过线性搜索.

但是,如果我们考虑顺序搜索查询并且这些查询不是完全随机的,则图片开始改变.想象一下,查询按排序顺序到达,即每个下一个查询的值都高于上一个查询.即查询也被排序.顺便说一句,它们不必全局且严格排序,查询序列可能不时"重置",即查询低值,但平均而言,后续查询应按递增顺序到达.换句话说,查询到达系列,每个系列按升序排序.在这种情况下,如果序列的平均长度与数组的长度相当,则线性搜索将大大优于二进制搜索.但是,要利用这种情况,您必须以增量方式实现搜索.很简单:如果下一个查询大于前一个查询,则无需从数组的开头开始搜索.相反,您可以从上一次搜索停止的位置进行搜索.最简单的实现(仅用于说明该想法)可能如下所示

static int linear(const int *arr, int n, int key)
{
  static int previous_key = INT_MIN;
  static int previous_i = 0;

  i = key >= previous_key ? previous_i : 0;

  while (i < n) {
    if (arr[i] >= key)
      break;
    ++i;
  }

  previous_key = key;
  previous_i = i;

  return i;
}

(免责声明:由于数组从外部作为参数到达的显而易见的原因,上述实现非常难看,而前一个搜索状态存储在内部.当然,这是在实践中这样做的错误方法.但同样,以上是为了说明这个想法,而不是更多).

请注意,O(N)无论系列的长度如何,使用上述方法处理每个有序查询序列的复杂性始终如一.使用二进制搜索,复杂性将是O(M * log N).因此,由于显而易见的原因,即M接近N,即查询到达足够长的有序序列,上述线性搜索将明显优于二进制搜索,而对于较小M的二元搜索将获胜.

此外,即使有序的查询序列不是很长,考虑到您必须使用线性搜索,上述修改可能仍会显着提高搜索性能.

PS作为有关问题结构的附加信息:

当您需要在有序的长度数组中执行搜索N并且事先知道查询将以[近似,平均]长度的有序序列到达时M,最佳算法将如下所示

1. 计算步幅值S = [N/M].将"捕捉" S到2的[最近]幂的值也可能是有意义的.将排序后的数组想象成一系列长度的块S- 所谓的S块.
2. 在接收到查询后,对可能包含查询值的S块执行增量线性搜索,即它是具有步幅的普通线性搜索S(当然,记住从上一次搜索中断的块开始).
3. 找到S块后,在S块中执行二进制搜索以查询查询值.

以上是最优化的增量搜索算法,从某种意义上说,它实现了重复搜索的渐近效率的理论极限.注意,如果值M小得多N,则算法"自动"将其自身转移到二分搜索,而当M接近N算法时,"自动"倾向于线性搜索.后者是有道理的,因为在这样的环境中,线性搜索比二分搜索明显更有效.

这一切只是为了说明诸如"对排序数组进行线性搜索总是无用的"这样的一揽子陈述,除了表明这些陈述的人缺乏知识之外别无其他.

Answer 3

由于您可以在最后一个有效条目之后放置已知值,因此添加一个额外的元素n + 1 = max以确保循环不会超过数组的末尾,而不必测试i <n.

static int
linear (const int *arr, int n, int key)
{
        assert(arr[n] >= key);
        int i = 0;
        while (arr[i] < key) {
                ++i;
        }
        return i;
}

您也可以尝试使用相同的sentinel值展开循环:

static int
linear (const int *arr, int n, int key)
{
        assert(arr[n] >= key);
        int i = 0;
        while (true) {
                if (arr [i++] >= key)
                        break;
                if (arr [i++] >= key)
                        break;
                if (arr [i++] >= key)
                        break;
                if (arr [i++] >= key)
                        break;
        }
        return --i;
}

Answer 4

首先,任何快速解决方案都必须使用矢量化来同时比较多个元素.

但是,到目前为止发布的所有矢量化实现都存在一个常见问题:它们具有分支.因此,他们必须引入阵列的块处理(以减少分支的开销),这导致小阵列的低性能.对于大型阵列,线性搜索比优化良好的二进制搜索更糟糕,因此优化它没有意义.

但是,可以在没有分支的情况下实现线性搜索.这个想法很简单:你想要的索引恰好是数组中少于你搜索的键的元素数.因此,您可以将数组的每个元素与键值进行比较,并将所有标志相加:

static int linear_stgatilov_scalar (const int *arr, int n, int key) {
    int cnt = 0;
    for (int i = 0; i < n; i++)
        cnt += (arr[i] < key);
    return cnt;
}

关于这个解决方案的一个有趣的事情是它会返回相同的答案,即使你洗牌数组=)虽然这个解决方案似乎相当慢,但它可以优雅地矢量化.下面提供的实现要求数组为16字节对齐.此外,必须使用INT_MAX元素填充数组,因为它一次消耗16个元素.

static int linear_stgatilov_vec (const int *arr, int n, int key) {
    assert(size_t(arr) % 16 == 0);
    __m128i vkey = _mm_set1_epi32(key);
    __m128i cnt = _mm_setzero_si128();
    for (int i = 0; i < n; i += 16) {
        __m128i mask0 = _mm_cmplt_epi32(_mm_load_si128((__m128i *)&arr[i+0]), vkey);
        __m128i mask1 = _mm_cmplt_epi32(_mm_load_si128((__m128i *)&arr[i+4]), vkey);
        __m128i mask2 = _mm_cmplt_epi32(_mm_load_si128((__m128i *)&arr[i+8]), vkey);
        __m128i mask3 = _mm_cmplt_epi32(_mm_load_si128((__m128i *)&arr[i+12]), vkey);
        __m128i sum = _mm_add_epi32(_mm_add_epi32(mask0, mask1), _mm_add_epi32(mask2, mask3));
        cnt = _mm_sub_epi32(cnt, sum);
    }
    cnt = _mm_hadd_epi32(cnt, cnt);
    cnt = _mm_hadd_epi32(cnt, cnt);
//  int ans = _mm_extract_epi32(cnt, 0);    //SSE4.1
    int ans = _mm_extract_epi16(cnt, 0);    //correct only for n < 32K
    return ans;
}

单个SSE2寄存器的最终减少只能在必要时使用SSE2实现,它不应该真正影响整体性能.

我在Intel Core2 Duo E4700上使用Visual C++ 2013 x64编译器进行了测试(很老,是的).使用rand()提供的元素生成大小为197的数组.所有测试的完整代码都在这里.这是执行32M搜索的时间:

[OP]
Time = 3.155 (-896368640) //the original OP's code
[Paul R]
Time = 2.933 (-896368640)
[stgatilov]
Time = 1.139 (-896368640) //the code suggested

OP的原始代码每秒处理1060万个阵列(每秒21亿个元素).建议的代码每秒处理2950万个数组(每秒58亿个元素).此外,建议的代码适用于较小的数组:即使对于15个元素的数组,它仍然比OP的原始代码快三倍.

这是生成的程序集:

$LL56@main:
    movdqa  xmm2, xmm4
    movdqa  xmm0, xmm4
    movdqa  xmm1, xmm4
    lea rcx, QWORD PTR [rcx+64]
    pcmpgtd xmm0, XMMWORD PTR [rcx-80]
    pcmpgtd xmm2, XMMWORD PTR [rcx-96]
    pcmpgtd xmm1, XMMWORD PTR [rcx-48]
    paddd   xmm2, xmm0
    movdqa  xmm0, xmm4
    pcmpgtd xmm0, XMMWORD PTR [rcx-64]
    paddd   xmm1, xmm0
    paddd   xmm2, xmm1
    psubd   xmm3, xmm2
    dec r8
    jne SHORT $LL56@main
$LN54@main:
    phaddd  xmm3, xmm3
    inc rdx
    phaddd  xmm3, xmm3
    pextrw  eax, xmm3, 0

最后,我想指出,只要间隔变小,就可以通过切换到所描述的矢量化线性搜索来更快地优化二进制搜索.

更新:有关此事的博客文章中可以找到更多信息.

Answer 5

好吧，你可以使用指针...

static int linear(const int *array, int arraySize, int key) {
    int i;

    for(i = 0; i < arraySize; ++i) {
        if(*array >= key) {
            return i;
        }

        ++array;
    }

    return arraySize;
}