摘要回忆器

Question

我是受到这个答案的启发才做这个的。

ex0 = 1；exN_ := exN = ex恩-1 + 0.5^n/n!；第二行的双赋值非常重要。这导致所有函数调用只计算一次。一旦它被初步评估，它将保存在exN中。

经过一番研究，看起来我刚刚重新发明了一个回忆录。

#include <unordered_map>
#include <functional>

template < auto callback,
           typename data_t,
           typename key_t = std::size_t >
class static_memoizer_t
{
public:
    using map_t = std::unordered_map< key_t,
                                      data_t >;
    using callback_t = decltype( callback );

    static_memoizer_t( ) = default;
    static_memoizer_t( static_memoizer_t const & ) = default;
    static_memoizer_t( static_memoizer_t && ) = default;
    static_memoizer_t & operator =( static_memoizer_t const & ) = default;
    static_memoizer_t & operator =( static_memoizer_t && ) = default;
    ~static_memoizer_t( ) = default;

    data_t operator[ ]( key_t const & key )
    {
        if( map.end( ) == map.find( key ) )
            return map[ key ] = callback( key );
        return map[ key ];
    }

    data_t operator[ ]( key_t const & key ) const
    {
        return map.at( key );
    }

private:
    map_t map;
};

template < typename data_t,
           typename key_t = std::size_t >
class dynamic_memoizer_t
{
public:
    using map_t = std::unordered_map< key_t,
                                      data_t >;
    using callback_t = std::function< data_t( key_t const & ) >;

    dynamic_memoizer_t( callback_t callback ):
        callback( std::move( callback ) )
    { }
    dynamic_memoizer_t( dynamic_memoizer_t const & ) = default;
    dynamic_memoizer_t( dynamic_memoizer_t && ) = default;
    dynamic_memoizer_t & operator =( dynamic_memoizer_t const & ) = default;
    dynamic_memoizer_t & operator =( dynamic_memoizer_t && ) = default;
    ~dynamic_memoizer_t( ) = default;

    data_t operator[ ]( key_t const & key )
    {
        if( map.end( ) == map.find( key ) )
            return map[ key ] = callback( key );
        return map[ key ];
    }

    data_t operator[ ]( key_t const & key ) const
    {
        return map.at( key );
    }

private:
    map_t map;
    callback_t callback;
};

其基本依据是存储昂贵功能的结果。我想为我最初的灵感添加对昂贵的递归函数的支持，但不确定如何处理。

用法：

int square_of( int i ) noexcept
{
    return i * i;
}

// static usage
using memoizer_t = static_memoizer_t< square_of, int, int >;
memoizer_t memoizer;
memoizer[ 2 ]; // calculates 2*2, returns 4
memoizer[ 2 ]; // pulls 2*2 from map

// dynamic usage
using memoizer_t = dynamic_memoizer_t< int, int >;
memoizer_t memoizer( square_of );
memoizer[ 2 ]; // calculates 2*2, returns 4
memoizer[ 2 ]; // pulls 2*2 from map

Answer 1

不幸的是，类的一个主要缺点是它只允许一个参数的函数。现在，这可以通过使用std::tuple和std::apply来缓解，但是它是一个丑陋的解决方案，因为它迫使类的用户指定元组类型，而对象的每次调用都需要一个std::make_tuple。

幸运的是，可以使用各种模板解决这一问题。

首先，这里是我们类的基本定义。

#include<tuple>
template<typename ReturnType, typename ... Args>
class Memoizer
{
};

现在，我们需要一种存储变量数和参数类型的方法。std::tuple是这方面的完美选择。

using tuple_type = std::tuple<Args...>;
using return_type = ReturnType;
using callback_type = std::function<return_type(Args...)>;
using map_type = std::unordered_map<tuple_type, return_type>;

现在，std::tuple不附带重载的std::hash。幸运的是这个答案提供了一个很好的实现。。

您的数据成员将成为

map_type map;
callback_type callback;

实现的核心在于operator()。

return_type operator()(Args&& ... args)
{
    auto arguments_tuple = std::make_tuple<Args...>(std::forward<Args>(args)...);
    if(map.find(arguments_tuple) == map.end())
    {
       std::cout << "Invoking function\n"; // for debugging
       map.insert({arguments_tuple, std::apply(callback, arguments_tuple)});
    }
    return map[arguments_tuple]; 
}

该方法接受参数，创建它们的元组，然后检查映射是否已经包含元组。如果没有，则使用std::apply (C++17功能)将条目插入到映射中。

用法可能如下所示：

int func(int x, int y)
{
    return x * y;
}

int main()
{
   Memoizer<int, int, int> mem{func};
   auto t1 = mem(2, 3);
   auto t2 = mem(2, 3);
   std::cout << t1 << '\n';
   std::cout << t2 << '\n';
}

产出如下：

Invoking function
6
6

全面执行如下：

https://godbolt.org/z/Eczq93

您还可以使用自定义类型作为参数，条件是对这些类型重载std::hash和operator==。