用空间换取时间规则：
1、扩展数据结构；
通常，通过给结构增加其他信息或改变结构内部的信息让它访问得更快能够减少对数据的常用操作所需的时间。
2、存储预先计算好的结果；
计算函数一次，然后存储计算结果能够减少昂贵函数的重新计算所需的成本。以后对该函数的请求就只需要通过表查找来完成，而不需要重新计算该函数。
3、高速缓存；
必须降低经常访问的数据的访问成本。
4、懒惰计算法；
除非需要，否则该策略永远都不会计算某个元素，这样可以避免计算不必要的元
素。
用时间换取空间规则：
5、压缩；
密集存储表示能够通过增加存储和检索数据所需的时间来降低存储成本。
6、解释程序；
通常，使用解释程序能够减少表示程序所需的空间，解释程序压缩表示相同的操作序列。
循环规则：
7、将代码移出循环；
最好不要在循环的每次迭代中都执行特定的操作，而是将它放在循环外部，仅仅执行一次。
8、合并测试条件；
高效的内部循环应该尽量少包含测试条件，最好只有一个。因此，程序员应该尽量使用其他退出条件模拟循环的一些退出条件。哨兵是该规则最常见的应用；在数据结构的边界上放一个哨兵来减少对是否已经查完整个结构的测试。
9、循环的解开；
解开一个循环能够消除修改循环下标的成本，同时也能够避免管道拖延、减少分支，并增加指令层的并发。
10、传输驱动的循环解开；
如果在普通的赋值中使用了一个成本很高的内部循环，那么通常通过重复这些代码改变对变量的使用能够消除这些赋值。特别是，删除赋值i=j，后面的代码必须将j视为i。
11、消除无条件分支；
在快速的循环中不应该包含无条件分支。通过“旋转”循环，在底部加上一个条件分支，能够消除循环结束处的无条件分支。
12、循环合并；
如果两个邻近的循环操作作用在同一个元素集上，那么最好合并这两个操作部分，仅仅使用一个循环控制操作。
逻辑规则：
13、利用代数恒等式；
如果逻辑表达式的计算非常昂贵，就使用比较廉价的代数等式表达式来替代它。
14、简化的单调函数。
测试几个变量的单调非递减函数是不是超过了特定的阈值，一旦达到了这个阈值就不需要计算任何变量。该规则的一个更加复杂的应用就是一旦达到了循环的目的就退出循环。
15、重新排序测试；
在组织逻辑测试的时候，应该将廉价的经常成功的测试放在昂贵的很少成功的测试前面。
16、预计算逻辑函数；
可以使用表示域的表的查找替代一个小的有限域中的逻辑函数。
17、消除布尔变量；
我们可以通过用if-else语句替代对布尔变量的v赋值来消除布尔变量，在if-else语句中一个分支表示v为真的情况，其他的表示v为假的情况。
过程规则：
18、压缩函数层次；
通常，重写函数并绑定过去的变量能够减少调用本身（非递归）函数集合元素的运行时间。
19、利用常用情况；
应该组织函数正确处理所有情况并高效处理普通情况。
20、协同例程；
通常，使用协同例程能够将多通道算法转换为单通道算法。
21、递归函数变化；
通过下面的转换能够减少递归函数的运行时间：将递归转化为迭代（如果某个函数仅仅包含一个对自身的递归调用，那么就没有必要将返回地址存储在栈中）；
如果函数的最后一步是递归调用自身，那么使用一个到其第一条语句的分支将替换该调用，这通常叫做消除尾递归。通常能够将该分支转换为循环，由编译器来执行这步优化。
通常使用辅助过程能够更高效地解决这些小的子问题，而不是将问题的大小变为0或1。
22、并发；
在基本的硬件条件下，构建的程序应该能够尽可能地利用并发。
表示规则：
23、初始化编译时间；
在程序执行之前，尽可能初始化变量。
24、利用代数恒等式；
如果表达式的计算非常昂贵，就应用较为便宜的代数恒等表达式替换它。尽量减少数组元素上的迭代循环，使用加法替代乘法。
25、消除通用子表达式；
如果连续两次计算了同一个表达式，并且它的所有变量都没有任何改动，那么就应该避免第二次计算，只需要排序第一次的计算结果并将它用于第二次计算中。现在编译器都能消除不包含函数调用的常用子表达式。
26、配对计算；
如果总是同时计算两个类似表达式，那么就应该建立一个新的过程，将它们成对计算。
27、利用单词（单元）并发；
使用基本计算机体系结构的完整数据路径宽度计算昂贵的表达式。
阅读(460) | 评论(0) | 转发(0) |
