编程技巧---代码调优法则

1.       空间换时间法则

 

1.1 修改数据结构

例如：计算球面距离：输入为球面上5000个点组成的集合S，再输入20000个点组成的序列，每个点实用经度和纬度表示，对于20000个点的序列，程序必须求出S中哪个点最接近它，距离使用球体中心与两个点的连线之间的夹角来度量。

直接计算需要用到大量的三角函数，开销很大，而两个点的距离随其欧氏距离单调增加（减小），故可将（经度，纬度）表示的数据结构变换为三维坐标形式，从而以更低的开销完成程序的需求。

 

1.2   存储预先计算好的结果

对于开销较大的函数，可以只计算一次，然后将计算结果存储起来以减少开销。以后再需要该函数时，可以直接查表而不需要计算。

 

1.3   高速缓存

最经常访问的数据，其访问开销应该是最小的，将这些数据进行缓存，从而减少时间开销。如linux内核通过高速缓存来分配经常分配和释放的对象。

 

1.4   懒惰求值

除非需要，否则不对任何一项求值。这一策略可以避免对不必要的项求值。

 

2.       时间换空间法则

 

2.1   堆积

密集存储表示可以通过增加存储和检索数据所需要的时间来减少存储开销。

例如：1. 使用稀疏数组，只增加一些访问时间，但大大减少了存储开销。

      2. 使用压缩算法，将数据压缩存储，增加使用时解压缩的计算开销。

      3. 使用共用体，通过在同一内存空间中存储不可能被同时调用的数据项来节省数据空间。

2.2 解释程序

使用解释程序通常可以减少表示程序所需的空间，例如：“格式信函编程”，当需要对很多不同的对象发送大部分内容相同的信件时，可使用一个信件模板，将不同的地方使用脚本语言等进行解释。

 

3.       循环法则

 

3.1   将代码移出循环

与其在循环的每次迭代时都执行一次某种计算，不如将其移到循环体外。

例如：在循环中交换两个数据的值

for(i = 0; i < 10; i++)

{

    swap(i , i+1);

}

优化1：直接将swap展开（C++的inline内联函数就是起这个作用），这样减少了过程活动记录压栈与出栈的开销。

for(i = 0; i < 10; i++)

{

int t = arr[i];   

arr[i] = arr[i+1];  

arr[i+1] = t;

}

优化2：局部变量t每次循环都在栈上重新分配，可将其移植循环外。

int t;

for(i = 0; i < 10; i++)

{

t = arr[i];

arr[i] = arr[i+1];

arr[i+1] = t;

}

 

3.2   合并测试条件

高效的内循环应该包含尽量少的测试条件，最好只有一个。故程序员应尽量用一些退出条件来模拟循环的其他退出条件。

哨兵是该法则的常见应用，在数据结构的边界上放一个哨兵以减少测试是否已搜索结束的开销。

展开循环：展开循环可以减少修改循环下标的开销，对于避免管道延迟（？？），减少分支以及增加指令级的并行也很有帮助。例如：将程序的循环次数减少，将大部分内容在循环内顺序实现。

删除赋值：如果内循环中很多开销来自普通的赋值，通常可以通过重复代码并修改变量的使用来删除这些赋值。例如：删除i=j后，后续代码必须将j是为i。

消除无条件分支：快速的循环中不应该包含无条件的分支。

 

3.3   循环合并

如果两个相邻的循环作用在同一个数组元素上，可以合并其运算部分，仅使用一组循环来控制操作。

例如：

int suma = 0,  mula = 1;

for(i = 0; i < 10; i++)

{

                   suma += a[i];

}

for(i = 0; i < 10; i++)

{

                   mula *= b[i];

}

可将循环合并为：

for( i = 0; i < 10; i++)

{

     suma += a[i];

     mula *= b[i];

}                                                                                                                                                                    

 

4.       逻辑法则

 

4.1   利用等价的代数表达式

如果逻辑表达式的求值开销太大，可将其替换为开销较小的等价代数表达式。

 

4.2   短路单调函数

如果我们想测试几个变量的单调非递减函数是否超过了某个特定的阈值，那么一旦达到了这个阈值就不需要计算任何变量了。

 

4.3   对测试条件进行重新排序

在组织逻辑测试的时候，将开销低，经常测试成功放在高开销的，很少成功的测试前面。

 

4.4   预先计算逻辑函数

在比较小的有限域上，可以用查表来取代逻辑函数。

 

4.5   消除布尔变量

可以使用if-else取代对布尔变量的赋值，从而消除程序中的布尔变量。

 

5．过程法则

 

5.1 打破函数层次

对于非递归，并且比较简单的函数，通常可以将其改为内联版本并固定传入的变量来缩短其运行时间。

 

5.2 高效处理常见情况

运用系统结构理论中的加快经常性事件原理，应使函数能正确处理所有情况，并能高效处理常见情况。

 

5.3 协同程序（？？）

使用协同例程能够将多躺算法转换为单趟算法

 

5.4 递归函数转换

递归函数的运行时间往往可以通过下面的转换来缩短：

1.       将递归重写为迭代。

2.       如果函数最后一步是递归调用其自身，则使用一个到其第一条语句的分支来替换该调用，即消除尾递归。

3.       解决小的子问题时，使用辅助过程通常比把问题的规模变为0或1更有效。（？？）

 

5.5 并行性

在底层硬件条件下，构建的程序应尽可能多的挖掘并行性。

 

6．表达式法则

 

6.1 利用等价的代数表达式。

如果表达式的求值开销太大，就将其替换为开销较小的等价代数表达式。

例如：用乘除法代替三角函数运算，乘（除）2的幂使用移位实现。

 

 

6.2 消除公共子表达式

如果两次对同一个表达式求值时，其所有的变量都没有改动，则不必要再次求值；可存储第一次计算的结果并用其取代第二次求值。

 

6.3 成对计算

如果经常需要对两个类似的表达式一起求值，应该建立一个新的过程，将他们成对计算。

 

6.4 利用计算机字的并行性

用底层计算机体系结构的全部数据路径宽度对高开销的表达式求值。

例如：使用char或int可以使位向量一次操作很多位。

 

以上内容参考《编程珠玑》（第二版）卷1附录D，其中有些内容还没弄懂，在文中以（？？）标注，如果您理解这些东西，烦请告知。