18分期摊还预期的计算成本：
1、基本思想就是：如果将来肯定要做某件事，并且这件事情耗时，提前把东西准备好，先做一部分。常用的使用场景有：
2、考虑一个大的数据集合，集合中元素不断变化。经常要取出里面的最大值，正常的做法是：每次调用的时候，计算出最大值，这可能是一个耗时的操作。既然是经常取出最大值，那我就实时（每次对集合增删改的时候）更新最大值，需要的时候直接就返回最大值了。
3、考虑stl中的vector，vector有5个元素，假设vector的内存刚好容纳5个元素，现在增加一个元素。那就意味着必须分配一块6个元素的内存，把原来的5个元素和新增的1个元素copy过来。这显然效率很低。解决办法是：预留一些内存。
4、较快的速度往往意味着较大的内存成本，需要在二者之间做出取舍。
例子：
这可以用超急评估来描述（over-eager evaluation）：在被要求之前就先把事情做下去。
考虑一个class template，用来表现数值数据的大型收集中心：
template<class NumericalType>
class DataCollection
{
public:
NumericalType min()const;
NumericalType max()const;
NumericalType avg()const;
...
};有三种方法实现这些函数。第一种是使用eager evaluation，在min、max或者avg函数被调用时才会检查所有数据，然后返回检查结果。第二种是使用lazy evaluation，于是我们令这些函数返回某些数据结构，这些函数的返回值真正派上用场时，才决定其适当数值。第三种是使用over-eager evaluation，也就是随时记录程序执行过程中数据集的最小值、最大值和平均值。一旦min、max或者avg被调用，便能立刻返回正确的值，无需再计算。如果min、max和avg常被调用，我们便能够分期摊还“随时记录数据群之最小、最大、平均值”的成本，而每次调用所付出的成本，将比eager evaluation或lazy evaluation低。
分期摊还可以通过缓存（cache）和预先取出（prefetching）来实现。下面详细介绍prefectching的做法。
prefetching的第一个例子是磁盘控制器的读写。经验显示，在磁盘中某处的数据如果被需要，那么其邻近的数据通常也会被需要，读小块数据的速度要快。因此从磁盘读数据都是预先读取出一大块数据。这就是locality of reference现象。而且在从磁盘中读取数据时，读一大块数据要比分成两三次每次
第二个例子是动态数组的实现。若不采用预先取出的策略，代码如下：
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;
}此做法是每次需要增加数组大小就调用new，但是new会调用operator new，这通常会调用底层操作系统，而系统调用往往比进程内的函数调用速度慢。因此代价昂贵。可以采用摊还策略。如果必须增加数组大小以接纳索引i，考虑到以后该数组大小可能还会再增加，因此可以把DynArray的大小调整到比它目前所需大小i再大一些，一般来说为两倍。
Comments NOTHING