C/C++编程：lazy evaluation

深碍√TFBOYSˉ_ 2023-01-12 11:42 113阅读 0赞

>  *  从效率的观点来看，最佳的计算就是根本不计算，那好，不过如果你根本就不用进行计算的话，为什么还在程序开始处加入代码进行计算呢?并且如果你不需要进行计算，那么如何必须执行这些代码呢？
>  *  关键是要懒惰。
>  *  还记得么？当你还是一个孩子时，你的父母叫你整理房间。你如果象我一样，就会说“好的“，然后继续做你自己的事情。你不会去整理自己的房间。在你心里整理房间被排在了最后的位置，实际上直到你听见父母下到门厅来查看你的房间是否已被整理时，你才会猛跑进自己的房间里并用最快的速度开始整理。如果你走运，你父母可能不会来检查你的房间，那样的话你就能根本不用整理房间了。
>  *  同样的延迟策略也适用于具有五年工龄的C++程序员的工作上。在计算机科学中，我们尊称这样的延迟为lazy evaluation（懒惰计算法）。当你使用了lazy evaluation后，采用此种方法的类将推迟计算工作直到系统需要这些计算的结果。如果不需要结果，将不用进行计算。。
>  *  也许你想知道我说的这些到底是什么意思。也许举一个例子可以帮助你理解。lazy evaluation广泛适用于各种应用领域，所以我将分四个部分讲述。

# **引用计数** #

class String { ... };            // 一个string 类
    
    String s1 = "Hello";
    
    String s2 = s1;                 / 调用string拷贝构造函数

通常string拷贝构造函数让s2被s1初始化后，s1和s2都有自己的”Hello”拷贝。这种拷贝构造函数会引起较大的开销，因为要制作s1值的拷贝，并把值赋给s2，这通常需要用new操作符分配堆内存(参见条款8)，需要调用strcpy函数拷贝s1内的数据到s2。这是一个eager evaluation（热情计算）：只因为到string拷贝构造函数，就要制作s1值的拷贝并把它赋给s2。然而这时的s2并不需要这个值的拷贝，因为s2没有被使用。

懒惰能就是少工作。不应该赋给s2一个s1的拷贝，而是让s2与s1共享一个值。我们只须做一些记录以便知道谁在共享什么，就能够省掉调用new和拷贝字符的开销。事实上s1和s2共享一个数据结构，这对于client来说是透明的，对于下面的例子来说，这没有什么差别，因为它们只是读数据：

cout << s1;                              // 读s1的值
    cout << s1 + s2;                         // 读s1和s2的值

仅仅当这个或那个string的值被修改时，共享同一个值的方法才会造成差异。仅仅修改一个string的值，而不是两个都被修改，这一点是极为重要的。例如这条语句：

s2.convertToUpperCase();

这是至关紧要的，仅仅修改s2的值，而不是连s1的值一块修改。

为了这样执行语句，string的convertToUpperCase函数应该制作s2值的一个拷贝，在修改前把这个私有的值赋给s2。在convertToUpperCase内部，我们不能再懒惰了：必须为s2（共享的）值制作拷贝以让s2自己使用。另一方面，如果不修改s2，我们就不用制作它自己值的拷贝。继续保持共享值直到程序退出。如果我们很幸运，s2不会被修改，这种情况下我们永远也不会为赋给它独立的值耗费精力。

总之**，除非你确实需要，不去为任何东西制作拷贝。**我们应该是懒惰的，只要可能就共享使用其它值。在一些应用领域，你经常可以这么做。

# **区别对待读取和写入** #

继续讨论上面的reference-counting string对象。来看看使用lazy evaluation的第二种方法。考虑这样的代码：

tring s = "Homer's Iliad";            // 假设是一个reference-counted string
    
    ...
    
    cout << s[3];                         // 调用 operator[] 读取s[3]
    s[3] = 'x';                           // 调用 operator[] 写入 s[3]

首先调用operator\[\]用来读取string的部分值，但是第二次调用该函数是为了完成写操作。我们应能够区别对待读调用和写调用，因为读取reference-counted string是很容易的，而写入这个string则需要在写入前对该string值制作一个新拷贝。

我们陷入了困难之中。为了能够这样做，需要在operator\[\]里采取不同的措施（根据是为了完成读取操作而调用该函数还是为了完成写入操作而调用该函数）。我们如果判断调用operator\[\]的context是读取操作还是写入操作呢？残酷的事实是我们不可能判断出来。通过使用lazy evaluation和proxy class，我们可以推迟做出是读操作还是写操作的决定，直到我们能判断出正确的答案。

# **Lazy Fetching****（懒惰提取）** #

假如程序中使用了一些包含很多字段的大型对象。这些对象的生存期超越了程序运行期，所以它们必须被存储在数据库里。每一个对象都有一个唯一的对象标识符，用来从数据库中重新获取对象：

class LargeObejct{              //大型持久对象
    public:
        LargeObejct(ObjectID id);  //从磁盘中恢复对象
        const string& field1() const; // field1的值
        int field2() const;           // feild2的值
        double field3() const;
        const string& field4() const;
        const string& field5() const;
        ...
    };

现在考虑一下从磁盘中恢复LargeObject的开销：

void restoreAndProcessObject(ObjectID id)
    {
      LargeObject object(id);                  // 恢复对象
      ...
    }

因为LargeObject对象实例很大，为这样的对象获取所有的数据，数据库操作开销将非常大，特别是如果从远程数据库中获取数据和通过网络发送数据时。而在这种情况下，不需要去读取所有的数据。比如，考虑这样一个程序：

void restoreAndProcessObject(ObjectID id){
    
        LargeObject object(id);
        if(object.field2() == 0){
            cout << "Object " << id << ": null field2\n";
        }
    }

这里仅仅需要field2()的值，所以为获取其他字段而付出的努力都是浪费。

LargeObject对象被建立时，不从磁盘上读取所有的数据，这样懒惰法解决了这个问题。不过这时建立的仅是一个对象“壳”，当需要某个数据时，这个数据才被从数据库中取回。这种“demand-paged”对象初始化的实现方法是:

class LargeObject {
    public:
      LargeObject(ObjectID id);
      const string& field1() const;
      int field2() const;
      double field3() const;
      const string& field4() const;
      ...
    private:
      ObjectID oid;
      mutable string *field1Value;               //参见下面有关
      mutable int *field2Value;                  // "mutable"的讨论
      mutable double *field3Value;
      mutable string *field4Value;
      ...
    };
    
    LargeObject::LargeObject(ObjectID id)
        : oid(id), field1Value(0), field2Value(0), field3Value(0), ...
    {}
    
    const string& LargeObject::field1()const{
        if(field2Value == 0){
            //从数据库中为field1读取数据，使得field1Value指向这个值
        }
        return *field2Value;
    }

对象中每个字段都用一个指向数据的指针来表示，LargeObject构造函数把每个指针初始化为空。这些空指针表示字段还没有从数据库中读取数值。每个LargeObject成员函数在访问字符指针之前必须检测指针的状态。如果为空，在对数据操作之前必须从数据库中读取对应的数据。

不过这里还有一个问题：在任何成员函数里都有可能需要初始化空指针使其指向真实的数据，包括在const成员函数里，比如field1.然而当你试图在const成员函数里修改数据时，编译器会出现问题。最好的非法是声明字段指针为mutable，这表示在任何函数里面它们都能被修改。

另外的问题是：LarObject里的指针，必须把这些指针都初始化为空，然后每次使用它们时都必须进行测试。这很麻烦而且很容易出错。这时可以使用smart指针自动完成这件事情。如果在LargeObject里使用smart指针，你也将发现不再需要用mutalbe声明指针。这只是暂时的，因为当你实现smart指针类时你最终会碰到mutalbe。

# **Lazy Expression Evaluation(****懒惰表达式计算)** #

有关lazy evaluation的最后一个例子来自于数字程序。考虑这样的代码

template<class T>
    class Matrix { ... };                         // for homogeneous matrices
    Matrix m1(1000, 1000);                   // 一个 1000 ＊ 1000 的矩阵
    Matrix m2(1000, 1000);                   // 同上
    ...
    Matrix m3 = m1 + m2;                     // m1＋m2

operator+会计算和返回m1与m2的和。这个计算量相当大（1000000次加法运算），当然系统也会分配内存来存储这些值。

解决：应该建立一个数据结构来表示m3的值是m1与m2的和，再用一个enum表示它们间是加法操作。很明显，建立这个数据结构比m1与m2相加要快许多，也能够节省大量的内存。

考虑程序后面这部分内容，在使用m3之前，代码执行如下：

Matrix m4(1000, 1000);
    
    ...                                           // 赋给m4一些值
    m3 = m4 * m1;

现在我们可以忘掉m3是m1与m2的和（因此节省了计算的开销），在这里我们应该记住m3是m4与m1运算的结果。不必说，我们不用进行乘法运算。因为我们是懒惰的，还记得么？

这个例子看上去有些做作，因为一个好的程序员不会这样写程序：计算两个矩阵的和而不去用它们，但是它实际上又不象看上去的那么做作。虽然好程序员不会进行不需要的计算，但是在维护中程序员修改了程序的路径，使得以前有用的计算变得没有了作用，这种情况是常见的。**通过定义使用前才进行计算的对象可以减少这种情况发生的可能性**（参见Effective C++条款32），不过这个问题偶尔仍然会出现

但是如果这就是使用lazy evaluation唯一的时机，那就太不值得了。一个更常见的应用领域是当我们仅仅需要计算结果的一部分时。例如假设我们初始化m3的值为m1和m2的和，然后象这样使用m3：

cout << m3[4];

很明显，我们不能再懒惰了，应该计算m3的第四行值。但是我们也不能雄心过大，我们没有理由计算m3第四行以外的结果；m3其余的部分仍旧保持未计算的状态直到确实需要它们的值。很走运，我们一直不需要。

我们怎么可能这么走运呢？矩阵计算领域的经验显示这种可能性很大。实际上lazy evaluation就存在于APL语言中。APL是在1960年代发展起来语言，能够进行基于矩阵的交互式的运算。那时侯运行它的计算机的运算能力还没有现在微波炉里的芯片高，APL表面上能够进行进行矩阵的加、乘，甚至能够快速地与大矩阵相除！它的技巧就是lazy evaluation。这个技巧通常是有效的，因为一般APL的用户加、乘或除以矩阵不是因为他们需要整个矩阵的值，而是仅仅需要其一小部分的值。APL使用lazy evaluation 来拖延它们的计算直到确切地知道需要矩阵哪一部分的结果，然后仅仅计算这一部分。实际上，这能允许用户在一台根本不能完成eager

evaluation的计算机上交互式地完成大量的计算。现在计算机速度很快，但是数据集也更大，用户也更缺乏耐心，所以很多现在的矩阵库程序仍旧使用lazy evaluation。

公正地讲，懒惰有时也会失败。如果这样使用m3：

cout << m3;

一切都完了，我们必须计算m3的全部数值。同样如果修改m3所依赖的任一个矩阵，我们也必须立即计算：

m3 = m1 + m2;                                // 记住m3是m1与m2的和
    
    m1 = m4;                                     // 现在m3是m2与m1的旧值之和！

这里我们我们必须采取措施确保赋值给m1以后不会改变m3。在Matrix赋值操作符里，我们能够在改变m1之前捕获m3的值，或者我们可以给m1的旧值制作一个拷贝让m3依赖于这个拷贝计算，我们必须采取措施确保m1被赋值以后m3的值保持不变。其它可能会修改矩阵的函数都必须用同样的方式处理。

因为需要存储两个值之间的依赖关系，维护存储值、依赖关系或上述两者，重载操作符例如赋值符、拷贝操作和加法操作，所以lazy evaluation在数字领域应用得很多。另一方面运行程序时它经常节省大量的时间和空间。

# 总结 #

以上这四个例子展示了lazy evaluation在各个领域都是有用的：能避免不需要的对象拷贝，通过使用operator\[\]区分出读操作，避免不需要的数据库读取操作，避免不需要的数字操作。但是它并不总是有用。就好象如果你的父母总是来检查你的房间，那么拖延整理房间将不会减少你的工作量。实际上，如果你的计算都是重要的，lazy evaluation可能会减慢速度并增加内存的使用，因为除了进行所有的计算以外，你还必须维护数据结构让lazy evaluation尽可能地在第一时间运行。在某些情况下要求软件进行原来可以避免的计算，这时lazy evaluation才是有用的。

lazy evaluation对于C++来说没有什么特殊的东西。这个技术能被运用于各种语言里，几种语言例如著名的APL、dialects of Lisp（事实上所有的数据流语言）都把这种思想做为语言的一个基本部分。然而主流程序设计语言采用的是eager evaluation，C++是主流语言。不过C++特别适合用户实现lazy evaluation，因为它对封装的支持使得能在类里加入lazy evaluation，而根本不用让类的使用者知道。

再看一下上述例子中的代码片段，你就能知道采用eager还是lazy evaluation，在类提供的接口中并没有半点差别。这就是说我们可以直接用eager evaluation方法来实现一个类，但是如果你用通过profiler调查（参见条款M16）显示出类实现有一个性能瓶颈，就可以用使用lazy evaluation的类实现来替代它（参见Effective C++条款34）。对于使用者来说所改变的仅是性能的提高（重新编译和链接后）。这是使用者喜欢的软件升级方式，它使你完全可以为懒惰而骄傲。

\+++