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
注:<编程珠玑>第十章代码优化有更详细的论述

|