《More Effective C++》阅读总结 - 缓式评估，超急评估(M17, M18)

Posted on | In

缓式评估

缓式评估(Lasy Evaluation)是指对用户虽然提出了某个运算需求，但是暂时用不到运算的结果，我们将此运算延缓到用户需要使用运算结果时。考虑以下代码：

1
2
3
4
5
6
7
8
9
template<class T>
class Matrix{
public:
    Matrix<T> operator + (const Matrix<T>& a, const Matrix<T>& b)
    {
        ...  \\(1)
    }
    ...
}

在代码块(1)中，我们可能会直接满足用户提出的加法计算需求，计算矩阵a和b对应位置元素之和，构成新的矩阵。事实上根据经验用户很可能不会需要用到新的矩阵的每一个元素，因此之前的计算存在冗余。例如用户可能这样使用Matrix库：

1
2
3
4
Matrix<int> a(1000,1000)，b(1000,1000), c(1000,1000);
... \\给a,b赋值
c = a + b;   \\ (1)
cout << c[1]; \\ (2)

在这种情况下，虽然用户提出了加法计算需求，即代码行(1),但是用户后续只需要计算结果的第一行即可，其他999*1000个元素的运算都是不必要的。

当然用户也有可能用到计算结果的全部部分：

1
2
3
4
Matrix<int> a(1000,1000)，b(1000,1000), c(1000,1000);
... \\给a,b赋值
c = a + b;   \\ (1)
cout << c; \\ (2)

以上案例表明了这样一个问题：用户提出的运算并不一定需要我们给出完整的结果。因此我们可以将运算延迟到需要的时候再进行，在用户提出运算需求时只是记录下来。矩阵的加法可以这样设计：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<class T>
class Matrix{
private:
    // (1)
    enum Operation{
        NONE=0,PLUS=1,MINUS,MULTIPLY,DIVIDE
    }
    // (2)
    Operation op;
    Matrix<T>* m1, *m2;
public:
    Matrix<T> operator + (const Matrix<T>& a, const Matrix<T>& b)
    {
        // (3)
        op = PLUS;
        m1 = &a;
        m2 = &b;
        return *this;
    }
    ...
}

我们通过增加一个枚举成员记录运算，并用两个指针成员记录运算成员,从而延迟了加法运算。在[]操作符的重载函数中，我们将进行具体的加法运算。

超急评估

超急评估(over-eager Evaluation)是指对用户虽然没有提出某个运算需求，但是我们估计将来很可能需要此运算，我们将此运算提前到用户需要使用运算结果时。仍然考虑矩阵类的设计，在科学计算中，我们有很大可能需要计算矩阵的范式，矩阵各元素之和，最值等。我们可以在调用这些统计函数时计算，也可以在对矩阵中元素赋值或者修改值的时候统计。后一种方法被称为超急评估。实现方法是使用缓存存储统计结果，如:

1
2
3
4
5
6
7
8
9
10
11
template<class T>
class Matrix{
private:
    T max, min, L1;
public:
    T min()
    {
        return min;
    }
    ...
}

在函数调用时我们只返回了缓存结果，实际的计算在构造函数，赋值操作的函数中。

超急评估将运算提前均摊到了类成员的修改函数中，总的效率并没有提升，但是用户的感受是：(1)虽然数据量很大，但是统计运算仍然非常快，没有随数据规模而增长 (2) 对类成员的修改没有明显变慢。由此可见，我们通过将运算均摊到了平时的每一次操作提升了用户体验。

超急评估还有两个著名的应用：

  • 磁盘控制器从磁盘中读取数据是读取整个sectors，尽管可能只需要其中的少量数据。这是因为有名的 locality of reference现象，即如果某处的数据被需要，通常其邻近的数据稍后也会被需要，因此我们通过提前读取一整块数据减少了寻址时间。
  • STL中vector扩容直接扩展到原来大小的2倍，尽管我们不需要这么多空间。

小结

  • 除了缓式评估(Lasy Evaluation)和超急评估(over-eager Evaluation)外还有即时评估(eager Evaluation)，它是指在用户提出计算需求时立刻完成，例如实现Matrix的min()函数时遍历所有元素找出最小值，这是我们最常用的方法。缓式评估牺牲了空间作为运算记录，缓式评估可能会得到了效率上的提升；超急评估牺牲了空间作为运算结果的缓存，超急评估提升了用户体验。这两种方法实现都比通常的即时评估复杂，究竟使用哪种方法取决于用户的关注点。
  • 虽然缓释评估在计算机科学中应用十分普遍，遗憾的是在日常生活中拖延几乎没有任何好处，工作量不会平白无故地消失，相反积压的工作可能会影响心情┭┮﹏┭┮. 日常生活中我们处理工作的最优解可能是分级处理机制吧，高优先级的超急评估，低优先级的懒式评估。