如何对代码进行调优？

一，空间换时间法则

1.1 修改数据结构

为了减少数据上的常见运算所需要的时间，我们通常可以在数据结构中增加额外的信息，或者修改数据结构中的信息使之更易访问

1.2 存储预先计算好的结果

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

1.3 高速缓存

最经常访问的数据，其访问开销应该使最小的

1.4 懒惰求值

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

二，时间换空间法则

2.1 堆积

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

2.2 解释程序

使用解释程序通常可以减少表示程序所需的空间，在解释程序中常见的操作序列以一种紧凑的方式表示

三，循环法则

3.1 将代码移除循环

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

3.2 合并测试条件

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

3.3 循环展开

循环展开可以减少修改循环下标的开销，对于避免管道延迟，减少分支以及增加指令级的并行性也都很有帮助

3.4 删除赋值

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

3.5 消除无条件分支

快速的循环中不应该包含无条件分支，通过“旋转”循环，在底部加上一个条件分支，能够消除循环结束处的无条件分支

3.6 循环合并

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

四，逻辑法则

4.1 利用等价的代数表达式

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

4.2 短路单调函数

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

4.3 对测试条件重新排序

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

4.4 预先计算逻辑函数

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

4.5 消除布尔变量

可以用if/else语句来取代对布尔变量v的赋值，从而消除程序中的布尔变量，在该if/else语句中，一个分支表示v为真的情况，另一个分支表示v为假的情况

五，过程法则

5.1 打破函数层次

对于非递归地调用自身的函数，通常可以通过将其改写为内联版本并固定传入的变量来缩短其运行时间

5.2 高效处理常见情况

应该使函数能正确处理所有情况，并能高效处理常见情况

5.3 协同程序

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

5.4 递归函数转换

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

5.4.1 将递归重写陈迭代

5.4.2 如果函数的最后一步使递归调用其自身，那么使用一个到其第一条语句的分支来替换该调用，消除尾递归

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

5.5 并行性

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

六，表达式法则

6.1 编译时初始化

在程序执行之前，应该对其尽可能多的变量初始化

6.2 利用等价的代数表达式

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

6.3 消除公共子表达式

如果两次对同一个表达式求值时，其所有变量都没有任何改动，我们可以用下面的方法避免第二次求值：存储第一次的计算结果并用其取代第二次求值

6.4 成对计算

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

6.5 利用计算机字的并行性

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