第四章，效率

条款18 分期摊还预期的计算成本

概述： 该条款提出，改善软件性能的方法是，让程序超前进度地做“要求以外”更多的工作。背后的哲学称为超急评估，在被要求之前就先把事情做下去。

例1： 数值数据的大型收集中心class template

template<class NumericalType>
class DataCollection{
public:
  NumericalType min() const;//返回数据群中的最小值
  NumericalType max() const;//返回数据群中的最大值
  NumericalType avg() const;//返回数据群中的平均值
  ...
}
/*对于这三个函数，应该如何将其设计得高效，提升程序的整体性能呢？
方案1：使用eager evaluation，函数被调用时才检查所有数据，返回检查结果

方案2：使用lazy evaluation，令函数返回某些数据结果，用来在这些函数的返回值真正被需要时再绝对其适当的值

方案3：使用over-eager evaluation，随时记录程序执行过程中数据集的最小值，最大值，平均值（用三个变量记录结果），一旦计算结果是计算过的，直接返回记录结果，减少计算成本
*/

上诉代码中的方案3是有效的，Over-eager evaluation背后的观念是，当某一计算是常常需要的，就建立一个缓存来记录结果，降低计算成本

例2： 获取由数据库存储的职员信息

//基于有缓存记录的方式，设计一个findCubicleNumber

int findCubicleNumber(const string& employeeName)
{
   typedef map<string, int> CubicleMap;
   static CubicleMap cubes; //缓存记录变量

   CubicleMap::iterator it = cubes.find(employeeName);

   if(it == cubes.end())
   {
       int cubicle = 
       //  the result of looking up employeeName's cubicle number in the database;

      cubes[employeeName] = cubicle;

      return cubicle;
   }
   else{
      return (*it).sencond;//没有使用it->sencond是因为it本身是对象不是指针，不保证->可施行于it身上，但STL明确要求“.”和“*”对iterators必须有效，这一点可以保证(*it).sencond可以有效运行
   }
}

上面两个例子都使用到了caching缓存记录这种做法，还有一种做法是Prefetching（预先取出）：一次读一大块数据比分成两三次每次读小块数据，速度上要快得多。

例3： 动态数组，设计operator[]使得非负索引值皆有效

template<class T>
class DynArray { ... };

DynArray<double> a;

a[22] = 3.5;
a[32] = 0;

template<class T>
T& DynArray<T>::operator[](int index)
{
   if(index < 0){
     throw an exception;
   }
   if(index > the current maximum index value){
     //call new to allocate enough additional memory so that index is valid;
   }

   return //the indexth element of the array;
}

上诉代码显然还有优化的空间，因为分配内存需要调用系底层操作系统函数，这往往比进程内的函数调用速度慢；此处可以使用Over-eager evaluation（超急评估）策略，把BynArray的大小调整到比它目前所需的大小更大一些，这样有概率让未来的扩张落入到此刻所增加的弹性范围内。

template<class T>
T& DynArray<T>::operator[](int index)
{
   if(index < 0) throw an exception;
   if(index > the current maximum index value){
     int diff = index - //the current maximum index value;

     //call new to allocate enougt additional memory so that index+diff is valid;
   }
   return //the indexth element of the array;
}

注意：over-eager evaluation策略由一个旋律贯穿之：最佳的速度往往导致较大的内存成本

总结：

lazy evaluation与over-eager evaluation并不矛盾。
当某些运算而其结果并不总是需要时，lazy evaluation可以改善程序效率；
当必须支持某些运算而其结果几乎总是被需要或常常被多次需要时，over-eager evaluation可以提升程序效率