本节课介绍了优化的一些法则
从以下四个方面介绍了优化法则
Data structures
包装与编码
包装的思想是把多个数据值存储在一个机器字中，而编码的思想是把数据值转换为需要更少比特表示的形式。例如日期字符串"September 11,2018"可以转换为下图中的结构体，其中year为13位，month为4位，day为5位：
增加额外属性
当要把链表A插入到链表B时，需要遍历到链表B的尾结点，这是个费时的操作。我们可以在链表B中增加一个属性记录尾结点的位置使插入操作达到常数级。
预先计算
下图计算二项式系数的函数性能很差，原因是当多次调用该函数时，做了许多无用的计算。
我们可以提前计算出每一个二项式系数，当要使用时，直接查表即可，如下图：
编译时初始化
设想一个场景，当程序调用上图的init_choose函数时，每次程序运行时都会计算一遍choose二维数组。这是没必要的，我们完全可以直接声明choose数组，以避免重复的计算。
但如果我们一个一个敲这些数据，那该多累啊！于是就有了元编程的思想，我们可以写一个程序，这个程序的输出就是上图中二维数组choose的声明。
缓存
缓存的思想太太太常见了，这里就不过多赘述了。
稀疏性
考虑矩阵乘以向量，如果矩阵中的零元素较多（稀疏矩阵），可以重新设计数据结构只存储非0元素以减少计算。
LOGIC
常数折叠与传播
当编译器的优化级别较高时，所有常量表达式都可在编译期计算出来（而不是在运行期）。
消除共用子表达式
上图中第四行的代码可以简化
代数恒等式
利用恒等式简化计算，下图是判断两个球是否碰撞的代码，用平方代替了开方：
短路
当已经知道结果时，没有必要继续无用的计算。
排序测试
考虑一系列的逻辑测试，排序测试的思想是优先测试那些经常成功的样例。由于逻辑运算符的短路性，可以减少计算，右图的性能更好，因为空格符和换行符出现的更为频繁。
创造快速路径
下图中是判断两个球是否碰撞的代码，增加了if语句创造快速路径。
结合测试
结合测试的思想是把多个测试结合为一个测试。
循环
代码移动
把不变的数据从循环中移出来以减少计算。这点在CSAPP中讲过。
哨兵
哨兵的作用是处理循环的边界问题。
循环展开
循环展开的思想是，让一次迭代计算多次，以减少迭代次数。
循环合并
把多个循环合并为一个循环。
消除不必要的循环
本质是减少循环次数。
函数
内联函数
内联函数可以减少函数调用时的开销。内联函数可以与宏一样高效。
消除尾递归
用迭代消除尾递归减少开销。
粗化递归
如下图，当数组规模较小时，直接用插入排序，规模较大时才用快速排序。
