17.Lazy evaluation

topic
2.6k 词

 
从效率的角度而言，最好的计算就是不计算。如果必须执行计算，我们可以拖到非计算不可的时候再计算。这种操作广泛适用于各个领域。

引用计数

1
2
3
class  { ... };
String s1 = "Hello";
String s2 = s1;

一般来说，s2被s1初始化后，s1与s2都有了自己的值，为了完成这个拷贝初始化，我们需要使用new来分配内存，需要调用strcpy函数拷贝数据等等，付出了极大的成本。但实际上此时的s2根本不需要执行拷贝操作，因为s2没被有被使用。

从lazy evaluation的角度而言，我们根本无需拷贝，只需要让s1与s2共享一个值即可。通过做一些记录以便了解哪些对象在共享哪些值，就省略了new与copy的开销。
当且仅当某个string被修改时，我们才需要执行真正的拷贝操作。例如当s2需要被修改，此时我们应该赶紧拷贝s1赋予s2，然后修改s2。

引用计数的具体实现机制见More Effective C++ 29，其核心原理就是lazy evaluation：除非你确实需要，否则不去为任何东西制作拷贝，能共享就共享。

区分读写

 
仍以上文带有引用计数的string举例：

1
2
3
4
String s = "Homer's Iliad";
...
cout << s[3]; //读取s[3]
s[3] = 'x'; //写入s[3]

读取并不会破坏共享性，但写入则需要对string值建立一个新拷贝。如果我们能够区分读取还是写入，在operator[]中采取不同的操作，那么效率必然会大幅度提升。但事实上我们不可能判断出调用operator[]是执行了读取还是写入，但可以配合More Effective C++ 30中的proxy class来推迟决定，直到我们了解当前是读取还是写入。

Lazy Fetching

 
假设当前程序使用了一些包含许多字段的大型对象，它们的生存期超越了程序运行期，所以它们必须被封存于数据库中，每一个对象都有一个唯一的标识符，以便于从数据库中重新获得对象：

1
2
3
4
5
6
7
8
9
10
class LargeObject {
public:
    LargeObject(ObjectID id);
    const string& field1() const;
    int field2() const;
    double field3() const;
    const string& field4() const;
    const string& field5() const;
    ...
};

如果要从数据库中获取该对象，有常规方法如下：

1
2
3
4
void restoreAndProcessObject(ObjectID id){
    LargeObject object(id);//构造对象
    ...
}

显然，由于对象实例太大，数据库以及网络的开销也将花费巨大，如果你仅仅只需要某一部分的数据：

1
2
3
4
5
6
void restoreAndProcessObject(ObjectID id){
    LargeObject object(id);
    if (object.field2() == 0) {
        cout << "Object " << id << ": null field2.n";
    }
}

这里我们只需要获取field2的值，获取其他的都是浪费，因此我们决定，当对象被建立时，不从数据库读取所有数据。建立的对象只是一个空壳，只有在需要某个数据时，该数据才从数据库中被读取：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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 double *field3Value;
    mutable string *field4Value;
    ...
};
LargeObject::LargeObject(ObjectID id)
:oid(id), field1Value(nullptr), field2Value(nullptr), field3Value(nullptr), ...
{}
const string& LargeObject::field1() const{
    if (field1Value == null) {
        ...//从数据库中为filed 1读取数据，使field1Value 指向这个值;
    }
    return *field1Value;
}

可以看出，每一个成员在访问成员前检查对应的指针是否为空，如为空则进行读取操作。mutable的使用时因为我们可能会在一个const成员函数内修改数据。

Lazy Expression Evaulation

 
考虑如下的矩阵运算：

1
2
3
4
5
6
template<class T>
class Matrix { ... };
Matrix<int> m1(1000, 1000); // 一个 1000 ＊ 1000 的矩阵
Matrix<int> m2(1000, 1000);
...
Matrix<int> m3 = m1 + m2; // m1＋m2

显然，eager evaluation差不多会执行1000000次加法。这并不为我们的lazy精神所提倡。
lazy evaluation认为应该建立一个数据结构表示m3的值是m1与m2发生交互的结果，再用一个enum表示矩阵间执行加法操作。如果接下来又有m4=m3*m1，那么同样地，我们会记录m4是m3与m1发生交互的结果，用一个enum表示乘法。
看起来以上操作并无用处，因为很少有人会列出表达式但不要求计算。但是事实上在很多情况下我们只需要计算矩阵的某一个元素或者某一列，因此我们完全没有理由计算出全部，每一次计算都仅仅针对被需求了解的未知量，剩余的部分将保持未计算的状态，直到确实需要它们。

总结

 
如果确实所有的任务都必须完成，那么lazy本质上并没有降低工作量，甚至还增加了内存使用与维护成本。从本质来说，它在当前只做关键的，需要使用的计算，仅此而已。