顺序查找的优化

看《programming pearls》里面有几段代码是关于加速查找算法，而且是顺序查找。感觉十分厉害，所以贴出来。

一般的顺序查找代码如下（算法1）：

#define MAXN 1000002
int n;
int x[MAXN];

int seqsearch1(int t)        /* 在数组x[0...n-1]中查找t */
{
    int i;
    for(i = 0; i < n; i++)
        if(x[i] == t)
            return i;
    return -1;
}

我们要写顺序查找，应该也就这么写的。既然都是顺序查找了，还能怎样加速这个程序呢？

算法2：

int seqsearch2(int t)
{
    int i;
    int hold = x[n];

    x[n] = t;                /* 将t放到x[0...n-1]之后，作为哨兵 */
    for(i = 0; ; i++)        /* 这样做的目的是：for循环里就没有i
        if(x[i] == t)
            break;
    x[n] = hold;
    if(i == n)
        return -1;
    else
        return i;
}

算法3：

int seqsearch3(int t)
{
    int i;
    int hold = x[n];

    x[n] = t;
    for(i = 0; ; i+=8)    /* 对的，循环展开，展开8次 */
    {
        if(x[i] == t)   {         break; }
        if(x[i+1] == t) { i += 1; break; }
        if(x[i+2] == t) { i += 2; break; }
        if(x[i+3] == t) { i += 3; break; }
        if(x[i+4] == t) { i += 4; break; }
        if(x[i+5] == t) { i += 5; break; }
        if(x[i+6] == t) { i += 6; break; }
        if(x[i+7] == t) { i += 7; break; }
    }
    x[n] = hold;
    if(i == n)
        return -1;
    else
        return i;
}

对这几段代码的性能测试结果如下：

[zxg@zxg-pc 5chp]$ ./a.out
100000
alg:1    n:100000    time:160.20ms              # 算法 seqsearch1
alg:2    n:100000    time:131.20ms              # 算法 seqsearch2
alg:3    n:100000    time:83.38ms               # 算法 seqsearch3
alg:4    n:100000    time:81.95ms               # 算法 seqsearch4, 该算法是对循环作了16次展开
200000
alg:1    n:100000    time:320.67ms
alg:2    n:100000    time:252.03ms
alg:3    n:100000    time:167.29ms
alg:4    n:100000    time:163.75ms

从上面可以看出，算法2，要比算法1快了一点点， 但循环展开算法加速了接近一倍，这是很可观的加速。我还试了对循环展开16次， 但发现和展开8次的比较没什么变化，说明循环展开也不是越多就越厉害。

上面的程序编译时没有打开优化选项，下面是用gcc -O3来编译的。

明显还是编译器的优化更牛一些。

[zxg@zxg-pc 5chp]$ ./opt-seq
100000
alg:1   n:100000        time:49.26ms
alg:2   n:100000        time:33.32ms
alg:3   n:100000        time:30.55ms
alg:4   n:100000        time:30.90ms
200000
alg:1   n:200000        time:104.13ms
alg:2   n:200000        time:81.35ms
alg:3   n:200000        time:83.84ms
alg:4   n:200000        time:75.47ms