1.整数求余.我万万没有想到过,求余运算符%也会成为被优化的对象,从前写下循环链表的例子:
int a[N];
void append(int m){
i = (i+1) % N;
a[i] = m;
}
看哪,多么简洁的代码,多么美妙,你几乎看不出什么破绽.然而,你听他说要把%给优化掉时,你会不会大跌眼睛?至少我是这样."尽管大多数算术运算需要花费大约10纳秒的时间,但%却要接近100纳秒,%的开销是及其昂贵的!"这样优化的建议是让你用便宜的逻辑判断取代%运算:
++i;
if(i==N) i=0;
a[i]=m;
这样如果这段代码是你的程序的核心的话,估计他能让你的程序快两倍.
2.对于循环的优化.这一点我同样感到惊讶,并非他有多么的神秘,其实很好懂,但是由于定向思维的影响,我们从来没有考虑过问题还可以这样优化:
第一,你可以通过避免循环的条件判断.
例如在一个数组中查找某个值,在a[N]找b,很明显顺序查找我们写的最多的代码是:
search(int a[],int b){
for(int i=0;i<N;++i){
if(a[i] == b) return i;
}
return -1;
}
同样你会多么的赞美,多么的满足,好像在没有比这个更完美的了,但是美神并不如此认为,他想下面的优化可以带来大约5%的提速:(多加一个空间使得数组长度为N+1)
search(int a[],int b){
a[N] = b;
for(int i=0;;++i){
if(a[i] == b) break;
}
if(i==N) return -1;
return i;
}
看哪,他确实比原来更好,因为每次循环从原来的执行两次判断(a[i]==b和i<N)变成现在的一次判断(a[i]==b),你可以理解,但是你未必能想到可以这样优化.
第二你可以减少循环所执行的次数.
这一点你也许不可理解,和我一样,他的策略是循环展开,我在想既然展开为什么要成为循环?但是你接着往下看的时候,你就会发现,这是二分查找最具优化性能的必要条件.上面循环优化的结果可能象这样:
search(int a[],int b){
a[N] = b;
for(int i=0;;i+=5){
if(a[i]==b) break;
if(a[i+1]==b) {i += 1; break;}
if(a[i+2]==b) {i += 2; break;}
if(a[i+3]==b) {i += 3; break;}
if(a[i+4]==b) {i += 4; break;}
}
if(i == N) return -1;
return i;
}
对于现代流水线技术的计算机,他可以避免流水线阻塞,减少分支,增加指令级并行.
3.向二分查找进发.
不必在回味我们的经典写法了,因为我们都很熟悉,何况他马上就要面临被优化的命运,呵呵.下面直解给出做法:
假设已排好序的数组a[N],其中N=1000,也就是我们常说的问题的规模为1000,首先我们取小于1000的但是2的最大幂值,很显然他是512,我们知道二分查找法的优良性能在于他每次让下一次问题规模减办,这是2的幂次的速度.
第一步的优化是放弃我们的上界下届标识变量,使用下届和距离来表示我们问题的空间:
i=512;
p=-1;
if(a[511]<b) p = 488;
while(i != 1){
i = i/2;
if(a[p+i]<b) p = p+i;
q = p+1;
if(q>1000 || a[q] != b) q = -1;
return q;
}
对于,这个问题我们知道i的取值,是一定的,因为2的若干次幂是一定,可以取值的范围就是{512,256,128,64,32,16,8,4,2,1}
因此我们有理由不使用循环,即使代码量增加一些,但是性能却提高不少,何乐不为?看:
p = -1;
if(a[p+512]<b) p += 512;
if(a[p+512]<b) p += 256;
if(a[p+512]<b) p += 128;
if(a[p+512]<b) p += 64;
if(a[p+512]<b) p += 32;
if(a[p+512]<b) p += 16;
if(a[p+512]<b) p += 8;
if(a[p+512]<b) p += 4;
if(a[p+512]<b) p += 2;
if(a[p+512]<b) p += 1;
q = p+1;
if(q>1000 || a[q] != b) q=-1;
return q;
你知道这有多妙,我只要增加一个语句便可以处理规模规模为2000的问题,再增加一条语句,你就可以处理规模为4000的语句,天哪,不仅如此你仅仅用到的只是一些简单判断,性能上已经是无可挑剔,如果你在处理一个很复杂的矩阵问题,我希望你能这样作,当然效率是不是关键因素要看你所在的项目,公司和你的工作而决定,但我有理由相信你能和我抱有一样感激的心情,上帝能给予如此美妙的东西赐给我们.
曹想华.2004/11/17
注:<编程珠玑>第十章代码优化有更详细的论述
