18.Over-eager evaluation

Posted on | In

前言

 
在上一节中，我们通过Lazy evalution来提高效率。但本节不存在Lazy，我们试图去让程序做的事情比被要求的还要多，通过这种方式来提高软件的性能。其核心就是本节主题Over-eager evaluation：在要求你做某些事情以前就完成它们。

问题实例

 
下述这个模板类表示一个存有大量数字型数据的集合：

1
2
3
4
5
6
7
8
template<class NumericalType>
class DataCollection {
public:
    NumericalType min() const;
    NumericalType max() const;
    NumericalType avg() const;
    ...
};

假设 min,max 和 avg 函数分别返回现在这个集合的最小值，最大值和平均值，有三种方法实现这些功能：

  • lazy evaluation
    确实需要返回值我们才去计算。
  • eager evaluation
    当函数被调用时，我们分析集合内所有数据，进行计算
  • over-eager evaluation
    随时跟踪目前集合的min，max，avg（每当集合发生变化即更新数据）因此函数调用时无需计算。

在频繁调用函数的情况下，我们把跟踪所花费的时间分摊于所有函数调用，那么实际花销反而比lazy与eager都要少。隐藏于其背后的思想是：如果一个计算需要频繁进行，那你应该设计某种数据结构进行高效处理，降低每一次计算的开销。

cache

 
over-eager evaluation最简单的实现是cache，缓存那些已经被计算出来并且以后可能仍然需要的值。
举例而言，办公室成员的所有信息都被放在数据库内，我们应该建立cache保存已经查到的信息，如此在以后需要时无需反复的查询数据库内部。
以下以办公人员隔间号作为信息举例：

1
2
3
4
5
6
7
8
9
10
11
12
int findCubicleNumber(const string& employeeName){
    typedef map<string, int> CubicleMap;
    static CubicleMap cubes;//cache
    auto it = cubes.find(employeeName);
    if (it == cubes.end()) {
        int cubicle = //search in database
        cubes[employeeName] = cubicle;
        return cubicle;
    }else {
        return (*it).second;
    }
}

prefetech

 
举例而言，每一次磁盘的读取并不是读你所需要的那一小块，而是直接读取一整块或者一个扇区。因为读取大块所需要的时间比读取好几个小块所需要的时间短，而且经验表明如果需要某一个地方的数据，那么也有可能会需要其周边的数据。（位置相关现象）正因为如此，系统设计者才有理由为指令与数据使用磁盘cache和内存cache，以及指令prefetch.
有可能你会说你对这种低级硬件处理没兴趣，那在数据结构中prefetch也有发挥作用。那就是vector的动态增长：一般而言，我们并不给vector分配恰好的cap，而是总是趋向于分配所需要的2倍大小，当vector饱和时，则再次分配当前cap两倍大小的cap.

总结

 
本节的核心思想在于：更快的速度需要更多的内存，也就是以空间换时间的策略。
当你需要支持某些操作但不需要立即得到结果时，使用lazy evaluation。
当你必须支持某些操作并且其结果总是被不止一次的重复需求时，记得caching与prefetching。