月归档：八月 2010

1、空间换时间法则 这个东西，稍微有点程序经验的人应该都接触过，比如在设计数据时候冗余了部分数据，避免关联表查询，减少开销，实际上也减少了查询时间，所谓空间换时间。还比如，我们将一个有点开销的计算结果存储起来，避免下次再次运算，减少时间消耗，再如，CPU的设计，设置了高速缓存，一级缓存，二级缓存，主存（通常所说的内存），其实一个硬盘和一个CPU也可以干活，只是干得不怎么样，因为硬盘和CPU之间速度实在是差别太大了，如是就有人想把可能要用到的数据预先加载到高速缓存或者主存中，慢慢形成了今天的个人计算机架构。 2、以时间换空间法则 这个其实也是天天在用的一个法则，只是一般技术人员看到“压缩”二字的时候，没联想到那么多，压缩就是最典型的拿时间换空间的例子，就是不断的重复前面已经存储过的存储地址，用来避免存取真实的数据。 3、循环法则 大部分稍微有点经验的人不会在同一个函数中循环两次同样的变量，但是仅限于同一个函数，假如在一个函数里调用了另外一个函数，那么就不一定了，很多人为了看似解耦的一个操作，在两个函数对同一个变量做了多次的循环。循环法则有几个比较经典细则： 第一、将代码移除循环，这是最容易想到的，当然，可以移除的条件是，每次循环都执行同样的某次操作。 第二、合并测试条件，高效的内循环应该包含尽量少的测试条件，最好只有一个，因此，程序员尽量用一些退出条件来模拟循环的其他退出条件。 第三、哨兵法则，在数据结构边界上放一个哨兵以减少测试是否已经搜索结束的开销。 第四、展开循环，展开循环可以减少修改循环下标的开销，对于避免管道延迟，减少分支以及增加指令级的并行性也有很大帮助。 第五、删除赋值，赋值的开销实际上在整个程序的执行过程中占的开销可以忽略不计，但假如你要在一个循环十万次的循环中赋值，那么开销就不能不计了，尽可能的在循环中减少赋值吧。 第六，消除无条件分支，快速的循环中不应该包含无条件分支，通过旋转循环，在底部加上一个条件分支，能够消除循环结束处的无条件分支。 第七、循环合并，如果你不小心做了傻事，那么合并两个对同一个变量循环操作吧 4、逻辑法则 利用等价的代数表达式。如果逻辑表达式的求值开销太大就将其替换为开销较小的等价代数表达式。 短路单调函数。如果我们想测试几个变量的单调非递减函数是否超过了某个特定的阈值，那么一旦达到这个阈值就不在需要计算任何变量了。 对测试机条件重新排序。在组织逻辑测试的时候，应该是降低开销的，经常成功的测试放在高开销的，很少成功的测试前面。 5、过程法则 打破函数层次。对于（非递归地）调用自身的函数，通常可以通过将其改写为内联版本并固定传入的变量来缩短其运行时间。 并行性。在底层硬件条件下，我们构建的程序应该尽可能多的挖掘并行性。 6、表达式法则 编译时初始化。在程序执行前，应该尽可能多的变量初始化。 利用等价的代数表达式。如果表达式的求值开销过大，就将其替换为开销更小的等价的代数表达式，比如换一种算法 消除公共子表达式。如果两次对同一个表达式求值，其所有变量都没有任何改动，那么我们可以用下面方法避免二次求值：存储第一次的计算结果并用其取代第二次求值。