通用备忘录基础设施

• 下载源代码 - 1.6 KB

引言

记忆化 - 在计算中，记忆化是一种优化技术，主要通过存储昂贵函数调用的结果，并在出现相同输入时返回缓存结果来加速计算机程序的运行。 © Wikipedia (http://en.wikipedia.org/wiki/Memoization)。

记忆化是动态规划的重要组成部分。这个想法很简单——一旦计算了某个结果，就将其存储起来，下次当你被要求计算相同的结果时，直接使用存储的值。在这里，我们需要澄清两个基本条件：计算结果是完全确定的，并且仅取决于输入参数。

伪代码

通常，简单的想法可以通过简单的设计和简单的实现来实现。对于记忆化来说，这也是事实。在 Wikipedia (http://en.wikipedia.org/wiki/Memoization) 上，我们甚至可以找到实现自动记忆化的伪代码。

 function memoized-call (F is a function object parameter)
     if F has no attached array values then
        allocate an associative array called values;
        attach values to F;
     end if;
 
     if F.values[arguments] is empty then
        F.values[arguments] = F(arguments);
     end if;
 
     return F.values[arguments];     
  end function

但是 C++ 的实现呢？在这里，事情要复杂得多，因为在现实生活中，我们处理的是真实类型。当你编写伪代码时，关联数组看起来非常简单。然而，当你编写 C++ 代码时，你必须知道类型。键的类型和值的类型。在我们的例子中，键是所有用作计算输入的参数的集合，而值是计算结果。

那么，我们将如何构建记忆化的基础设施呢？答案几乎是立刻的——我们将使用模板。直接的方法是提供类型列表，该列表将包含计算结果的类型（我们关联数组中的值）以及一个或多个输入参数的类型（我们关联数组中的键）。另一个“锦上添花”的功能是为记忆化和非记忆化版本提供单一 API。到目前为止，都还不错，但我们的基础设施的 API 需要提供所有这些类型，这在我看来会有点烦人且不用户友好。此外，我们需要提供一个函数作为附加参数，该函数将实现原始计算逻辑（以支持单一 API 功能）。

我们能做得更好吗？我们会尝试 :) 而且我们会成功！

API 和示例

假设我们有一个模板类Memoize，应该像下面的示例一样使用。

这里我们有一个结构体 MagicCircle，其中有一个方法Func，它接收Coordinates和String作为参数，经过非常漫长而复杂的数学计算后返回Radius和Color。不要试图找出数学计算的逻辑，这不是重点。我们只是想通过这个例子，使用非平凡的输入类型（std::pair和std::string）和非平凡的返回类型（某个结构体），来演示记忆化基础设施的易用性。

#pragma once

#include <cstdint>
#include <utility>    
#include <string>
#include <limits>
#include <random>

#include "Memoize.h"

enum class Color { RED, GREEN, BLUE };
using Coordinates = std::pair < uint32_t, uint32_t >;

struct MagicColorResult
{
    uint32_t radius;
    Color color;
};

struct MagicCircle : public Memoize< MagicCircle >
{
    static MagicColorResult Func(Coordinates coord, std::string str)
    {
        // Do not try to understand internals of this method
        // That just represents some long and complex calculations.
        
        /************************************************************/
        /**/ MagicColorResult res;
        /**/
        /*  LONG AND COMPLEX MATHEMATICAL CALCULATIONS .....
        /*     ................................................
        /*     ................................................
        /*     ................................................
        /*     ................................................
        /*     ................................................
        /*     ................................................
        */
        /**/ std::random_device rd;
        /**/ std::mt19937 gen(rd());
        /**/ std::uniform_int_distribution<uint32_t>
        /**/ dis(std::numeric_limits<uint32_t>::lowest(),
        /**/     std::numeric_limits<uint32_t>::max()
        /**/    );
        /**/
        /*   After long and complex math we set the resut; */
        /**/ res.radius = dis(gen);
        /**/ res.color  = Color::GREEN;
        /************************************************************/

        return res;
    }
};

那么，让我们看看我们这里有什么

1. 在结构体MagicCircle的定义中，我们继承自类Memoize，并将MagicCircle本身作为模板参数提供。
2. 我们实现静态方法Func，它接收一些（许多）参数，并返回某种类型的计算结果。

这些是使用记忆化基础设施的所有要求。继承自类Memoize（并提供模板参数），并实现静态方法Func。

就是这样。

我们不关心Func接收多少以及什么类型的参数作为输入，也不关心输出类型是什么。

现在，让我们看看如何使用它

MagicColorResult res1 = Memoize<MagicCircle>::Func(Coordinates{7,2}, std::string(" Original Dummy "));
MagicColorResult res2 = Memoize<MagicCircle>::Func(Coordinates{7,2}, std::string(" Another Dummy  "));
MagicColorResult res3 = Memoize<MagicCircle>::Func(Coordinates{7,2}, std::string(" Original Dummy "));

为了调用MagicCircle的计算，使用记忆化基础设施，我们只需要调用Memoize<MagicCircle>::Func(...)，而不是MagicCircle::Func(...)方法本身。然后魔法就会发生：对于前两次调用，使用“第一次出现的”参数，实际计算将被执行。但是对于第三次调用，参数与第一次调用相同，不会执行任何计算，而是返回记忆化的结果。

实现

现在是时候转向Memoize的实际实现了。

#pragma once

#include <tuple>
#include <map>

template < typename T > struct Memoize
{
    template <typename... Args> static auto Func(Args&&... args) 
                          -> decltype(T::Func(std::forward<Args>(args)...))
    {
        using INPUT = std::tuple<Args...>;

        using RESULT = decltype(T::Func(std::forward<Args>(args)...));

        static std::map< INPUT, RESULT > repository;

        auto key = std::make_tuple(std::forward<Args>(args)...);

        auto it = repository.find(key);

        if (it != repository.end())
        {
            return it->second;
        }

        else
        {
            auto result = T::Func(std::forward<Args>(args)...);

            repository[key] = result;

            return result;
        }
    }
};

正如我们所见，Memoize将一个类作为模板参数，该类只有一个要求——这个类必须有一个静态方法Func。

在内部，Memoize定义了自己的静态方法Func，其输入参数类型和输出参数类型与模板参数类中的原始Func相同。为了实现这一点，我们使用可变模板（C++11）作为输入参数，并使用decltype（C++11）作为输出类型。没有显式传递类型。编译器为我们完成了这项工作——Memoize::Func的所有类型（输入和输出）都由编译器从派生类Func的定义中推断出来。

实现本身与伪代码非常相似。我们将计算结果存储在关联数组（在我们的例子中是std::map）中，并由输入参数的组合索引。在Func调用时，我们通过查找由输入参数组合索引的关联数组来查看是否已经计算过完全相同的参数。如果我们找到了结果，我们就直接返回它，而不进行实际计算。如果我们没有找到——我们就调用原始的Func，它负责实际计算，并存储结果。

这里唯一可能感兴趣的细节是索引本身。为了索引，我们使用基于输入类型的std::tuple。再次提醒，tuple的顺序操作是通过tuple类型的字典序定义的。因此，输入参数中的每个特定类型都必须具有比较运算符。

递归示例

正如我所写，记忆化是动态规划的重要组成部分。这里有一个如何使用Memoize基础设施进行动态规划阶乘计算的示例。

#pragma once

#include <cstdint>

#include "Memoize.h"

class Factorial : public Memoize<Factorial>
{
public:
    static uint32_t Func(int i)
    {
        if (i == 0)
        {
            return 1;
        }

        return i * Memoize::Func(i - 1);
    }
};

请注意，对于递归调用，我们应该调用Factorial类自身中的Func方法，而不是Memoize::Func的实现。

外部使用与前面的示例类似

Memoize<Factorial>::Func(10);
Memoize<Factorial>::Func(11);

对于第二次调用，只会执行一次计算，即 10*11。

备注

正如我们所见，此实现中使用了 C++11 的一些高级特性。请注意，并非所有编译器都完全支持 C++11。此代码已使用 MSVC 2014 CTP 编译器实现和测试。