可调用对象的惰性求值和记忆化求值
4.93/5 (5投票s)
我喜欢工作。它让我着迷。我可以坐着看它几个小时。（匿名）
引言
本文介绍了两个类。它们可以封装任何可调用对象（普通函数、函数对象、静态成员函数、普通成员函数等），并以延迟的方式（恰好在需要结果时）调用它们，并且还可以高效地调用它们（带或不带记忆化）。这些类可能仅在这些可调用对象包含非常昂贵或耗时的操作时才有用。否则，它的使用可能会增加不必要的开销。
背景
函数不是一个惰性对象。它实际上是一个非常勤奋的对象。你无法直接（通过复制或移动）将它（别想低级的函数指针）在代码中传递。你通常必须将其包含在你的作用域中，然后调用它，假设（当然）你已经在同一作用域中获得了所有参数的访问权限。这是函数的一般且合理的使用方式。
为了在上述意义上传递函数（或任何其他可调用对象，如 lambda、普通成员函数和静态成员函数等），你可以将其包装在一个合适的对象中。std::function 是一个不错的选择。你可以将任何可调用对象包装在 std::function 对象中，并在需要时将其 along 代码 along。
到目前为止一切顺利。但我们可以以较低的成本包含一些有用的功能。例如：
- std::function （及其包含的可调用对象）在调用时需要访问参数。有时参数输入和函数调用发生在不同的代码位置。将这些参数包装在同一个函数包装器中会很有趣。
- 如果我们对同一组参数的结果求值两次，再次调用 std::function 对象将是时间和资源的巨大浪费。如果我们至少能存储最后一次求值的结果，那将是好的。
- 对于非常耗时的可调用对象，对于一组经常使用的参数，对结果进行记忆化将显著提高整体效率。
本文介绍的 lazy_evaluator<> 类实现了前两个改进，而 memoized_lazy_evaluator<> 类实现了改进 1 和 3。
使用代码
无记忆化的延迟调用
让我们从一个简单的代码示例开始。要惰性地调用一个普通函数，我们可以这样写：
#include <iostream>
#include "lazy_evaluator.h"
// Standalone function
int costly_function(int arg)
{
// Suppose a very costly function whose final output is "result".
// After a very complicated computation:
int result=2*arg;
return result;
}
int main()
{
// Lazy evaluator from a standalone function.
// (In this example, arguments are provided in constructor).
lazy_evaluator<int(int)> func1(costly_function, 2);
// We can copy and move the prior object as much
// as we want all along our code.
// Eventually, we'll need to evaluate our costly function somewhere:
std::cout << "func1(2) = " << func1.value() << std::endl;
// Once evaluated, the result is stored in the very object so
// further calls to value() have no overhead:
std::cout << "func1(2) = " << func1.value() << std::endl;
// We can reset our evaluator simply by providing new arguments:
func1.set_args(3);
// As before, no operations are executed until we reclaim the result:
std::cout << "func1(3) = " << func1.value() << std::endl;
return 0;
}
请注意，lazy_evaluator<> 是使用可调用对象的调用签名实例化的（在上面的例子中是 int(int)）。
在参数的数量或类型上没有限制。在下面的示例中，我们正在封装一个普通成员函数（借助 std::bind）
#include <functional>
#include <iostream>
#include "lazy_evaluator.h"
// Ordinary member function
class costly_function_om
{
double a_;
public:
explicit costly_function_om(double a) :
a_(a)
{}
double func(int arg1, double arg2)
{
// Suppose a very costly function whose final output is "result".
// After a very complicated computation:
double result=2.0*arg1+arg2+a_;
return result;
}
};
int main()
{
// Lazy evaluator from an ordinary member function.
// (In this example, arguments are not provided in constructor,
// but you can include them if you will).
costly_function_om instance(1);
lazy_evaluator<double(int, double)> func3(
std::bind(
&costly_function_om::func,
instance,
std::placeholders::_1,
std::placeholders::_2
)
);
func3.set_args(2, 3.0);
std::cout << "func3(2, 3.0) = " << func3.value() << std::endl;
return 0;
}
你可以在随附项目中的 sample_le.cpp 中找到更多 lazy_evaluator<> 的用法示例。除了使用 std::bind 等特殊构造外，它的使用直观且非常简单。
带记忆化的延迟调用
现在让我们使用记忆化。其目的是避免对一个非常耗时的可调用对象使用相同的参数集进行两次求值。对于一个独立的函数，我们有：
#include <iostream>
#include "memoized_lazy_evaluator.h"
// Standalone function
int costly_function(int arg)
{
// Suppose a very costly function whose final output is "result".
// After a very complicated computation:
int result=2*arg;
return result;
}
int main()
{
// Memoized lazy evaluator from a standalone function.
// (In this example, arguments are provided in constructor).
memoized_lazy_evaluator<int(int)> func1("costly_function", costly_function, 2);
// We can copy and move the prior object as much
// as we want all along our code.
// Eventually, we'll need to evaluate our costly function somewhere:
std::cout << "costly_function(2) = " << func1.value() << std::endl;
// Once evaluated, the result is stored in a static repository so
// further calls to value() have no overhead:
std::cout << "costly_function(2) = " << func1.value() << std::endl;
// We can reset our evaluator simply by providing new arguments:
func1.set_args(3);
// As before, no operations are executed until we reclaim the result:
std::cout << "costly_function(3) = " << func1.value() << std::endl;
return 0;
}
在上面的示例中，func1 存储了每一次求值，这样，给定相同的参数集，结果将从一个静态存储库中检索。在深入研究这个存储库结构之前，让我们再展示一个例子，这次应用于 lambda：
#include <iostream>
#include "memoized_lazy_evaluator.h"
int main()
{
// Memoized lazy evaluator from an anonymous function.
// (In this example, arguments are not provided in constructor,
// but you can include them if you will).
memoized_lazy_evaluator<double(int)> func5(
"costly_lambda",
[](int arg) -> double {return 2.0*arg;} // Very costly lambda function.
);
func5.set_args(2);
std::cout << "costly_lambda(2) = " << func5.value() << std::endl;
return 0;
}
从前面的两个示例可以看出，memoized_lazy_evaluator<> 的构造函数始终要求一个字符串作为第一个参数。该字符串标签由用户任意指定，但必须与同一可调用对象双射关联。换句话说：每个附加到（例如）costly_function 的 memoized_lazy_evaluator<> 对象都必须使用相同的字符串标签构造（无论该标签名称是什么）。否则，记忆化机制将无法高效工作。
记忆化存储库
为了理解之前的约束，现在是时候展示静态存储库结构了。这是它在代码中的声明方式：
template <typename R, typename... Args>
class memoized_lazy_evaluator<R(Args...)>
{
typedef std::tuple<Args...> args_t;
typedef std::map<args_t, R> table_t;
typedef std::map<std::string, table_t> repository_t;
static repository_t repository;
// ...
};
如果你更喜欢以图形方式查看上述结构：
正如你所看到的，对于每个 R(Args...) 调用签名都有一个静态存储库，因此，无论它们的实际类型如何，所有接受相同参数类型并返回相同结果类型的可调用对象都存储在同一个存储库中。为了区分一个可调用对象与任何其他对象，memoized_lazy_evaluator<> 的构造函数需要标签。如前所述，标签名称由用户任意指定，但以标签的名称命名关联的可调用对象是合理的。对于普通成员函数必须格外小心。看看这个例子：
#include <functional>
#include <iostream>
#include "memoized_lazy_evaluator.h"
// Ordinary member function
class costly_function_om
{
double a_;
public:
explicit costly_function_om(double a) :
a_(a)
{}
double func(int arg1, double arg2)
{
// Suppose a very costly function whose final output is "result".
// After a very complicated computation:
double result=2.0*arg1+arg2+a_;
return result;
}
};
int main()
{
costly_function_om instance(1);
memoized_lazy_evaluator<double(int, double)> func3(
"costly_function_om::func",
std::bind(
&costly_function_om::func,
instance,
std::placeholders::_1,
std::placeholders::_2
)
);
return 0;
}
"costly_function_om::func" 是我们记忆化结构的良好标签吗？绝对不是，因为可调用对象依赖于 a_。一个更明智的选择可能是（例如）： "costly_function_om::func;a_=1"。
延迟求值器作为类成员
可以将本文描述的类型用作类成员。lazy_evaluator<> 和 memoized_lazy_evaluator<> 都可以进行复制和移动构造，并且可以进行复制和移动赋值。
当它们作为默认构造类的成员包含时，必须格外小心。在这种情况下，必须提供一个 setter，以便在求值之前附加一个可调用对象。否则，在调用 value() 时将抛出 std::runtime_error。
源代码
lazy_evaluator<> 和 memoized_lazy_evaluator<> 的实现代码 已附上，以及它们对应的主要示例代码。
代码使用 Code::Blocks 编写，并使用 MinGw gcc (v.4.8.1-4) 编译。
参考文献
来自 codeproject.com
来自 stackoverflow.com