Написание универсальной функции запоминания в C++11

Question

Ищете способ реализовать универсальную универсальную функцию запоминания, которая возьмет функцию и вернет запомненную версию того же самого?

Ищите что-то вроде @memo (с сайта Norving) в python.

def memo(f):
    table = {}
    def fmemo(*args):
        if args not in table:
            table[args] = f(*args)
        return table[args]
    fmemo.memo = table
    return fmemo

В общем, есть ли способ выразить универсальные и повторно используемые декораторы в C++, возможно, используя новые функции C++11?

Answer 1

Компактный, возвращающий лямбду:

template <typename R, typename... Args>
std::function<R (Args...)> memo(R (*fn)(Args...)) {
    std::map<std::tuple<Args...>, R> table;
    return [fn, table](Args... args) mutable -> R {
        auto argt = std::make_tuple(args...);
        auto memoized = table.find(argt);
        if(memoized == table.end()) {
            auto result = fn(args...);
            table[argt] = result;
            return result;
        } else {
            return memoized->second;
        }
    };
}

В C++14 можно использовать обобщенный вывод типа возврата, чтобы избежать дополнительной косвенности, налагаемой возвратом std::function,

Делая это полностью общим, позволяя передавать объекты произвольной функции, не заключая их в std::function первое оставлено в качестве упражнения для читателя.

Answer 2

Правильный способ запоминания в C++ - это смешивать Y-комбинатор.

Ваша базовая функция нуждается в модификации. Вместо непосредственного вызова он принимает шаблонизированную ссылку на себя в качестве первого аргумента (или std::function<Same_Signature> рекурсия как первый аргумент).

Начнем с Y-комбинатора. Затем мы добавляем в кеш на operator() и переименуйте его в memoizerи дать ему фиксированную подпись (для таблицы).

Осталось только написать tuple_hash<template<class...>class Hash> это делает хэш на кортеже.

Тип функции, которую можно запомнить: (((Args...)->R), Args...) -> R, который делает памятку типа ( (((Args...) -> R), Args...) -> R ) -> ((Args...) -> R), Использование Y-комбинатора для создания "традиционной" рекурсивной реализации также может быть полезным.

Обратите внимание, что если функция memoised изменяет свои аргументы во время вызова, то Memoizer будет кэшировать результаты в неправильном месте.

struct wrap {};

template<class Sig, class F, template<class...>class Hash=std::hash>
struct memoizer;
template<class R, class...Args, class F, template<class...>class Hash>
struct memoizer<R(Args...), F, Hash> {
  using base_type = F;
private:
  F base;
  std::unordered_map< std::tuple<std::decay_t<Args>...>, R, tuple_hash<Hash> > cache;
public:

  template<class... Ts>
  R operator()(Ts&&... ts) const
  {
    auto args = std::make_tuple(ts...);
    auto it = cache.find( args );
    if (it != cache.end())
      return it->second;

    auto&& retval = base(*this, std::forward<Ts>(ts)...);

    cache.emplace( std::move(args), retval );

    return decltype(retval)(retval);
  }
  template<class... Ts>
  R operator()(Ts&&... ts)
  {
    auto args = std::tie(ts...);
    auto it = cache.find( args );
    if (it != cache.end())
      return it->second;

    auto&& retval = base(*this, std::forward<Ts>(ts)...);

    cache.emplace( std::move(args), retval );

    return decltype(retval)(retval);
  }

  memoizer(memoizer const&)=default;
  memoizer(memoizer&&)=default;
  memoizer& operator=(memoizer const&)=default;
  memoizer& operator=(memoizer&&)=default;
  memoizer() = delete;
  template<typename L>
  memoizer( wrap, L&& f ):
    base( std::forward<L>(f) )
  {}
};

template<class Sig, class F>
memoizer<Sig, std::decay_t<F>> memoize( F&& f ) { return {wrap{}, std::forward<F>(f)}; }

живой пример с жестко закодированной хэш-функцией, основанной на этом посте.

auto fib = memoize<size_t(size_t)>(
  [](auto&& fib, size_t i)->size_t{
    if (i<=1) return 1;
    return fib(i-1)+fib(i-2);
  }
);

Answer 3

Я боролся с той же проблемой. Я создал макрос, который также поддерживает (с небольшими изменениями в рекурсивном коде) рекурсию. Вот:

#include <map>
#include <tuple>
#define MEMOIZATOR(N, R, ...)                               \
R _ ## N (__VA_ARGS__);                                     \
std::map<std::tuple<__VA_ARGS__>, R> _memo_ ## N;           \
template <typename ... Args>                                \
R N (Args ... args) {                                       \
    auto& _memo = _memo_ ## N;                              \
    auto result = _memo.find(std::make_tuple(args...));     \
    if (result != _memo.end()) {                            \
        return result->second;                              \
    }                                                       \
    else {                                                  \
        auto result = _ ## N  (args...);                    \
        _memo[std::make_tuple(args...)] = result;           \
        return result;                                      \
    }                                                       \
}                                                           

Использование действительно просто:

MEMOIZATOR(fibonacci, long int, int);

long int _fibonacci(int n) { // note the leading underscore 
                             // this makes recursive function to go through wrapper
    if (n == 1 or n == 2) {
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

fibonacci(40) // uses memoizator so it works in linear time 
              // (try it with and without memoizator)

Посмотрите это в действии: http://ideone.com/C3JEUT:)

Answer 4

Несмотря на то, что @KerrekSB опубликовал ссылку на другой ответ, я, хотя и добавлю свой ответ в кольцо (вероятно, он немного менее сложен, чем связанный ответ, хотя по сути он очень похож):

#include <functional>
#include <map>
#include <tuple>
#include <utility>

/*! \brief A template functor class that can be utilized to memoize any 
*          given function taking any number of arguments. 
*/
template <typename R, typename... Args>
struct memoize_wrapper
{
private:

    std::map<std::tuple<Args...>, R> memo_;
    std::function<R(Args...)> func_;

public:

    /*! \brief Auto memoization constructor.
     *  
     *  \param func an the std::function to be memoized.
    */
    memoize_wrapper(std::function<R(Args...)> func)
      : func_(func)
    { }

    /*! \brief Memoization functor implementation.
     *  
     *  \param a Argument values that match the argument types for the 
     *           (previously) supplied function. 
     *  \return A value of return type R equivalent to calling func(a...).
     *          If this function has been called with these parameters
     *          previously, this will take O(log n) time.
    */
    R operator()(Args&&... a)
    {
        auto tup = std::make_tuple(std::forward<Args>(a)...);
        auto it = memo_.find(tup);
        if(it != memo_.end()) {
            return it->second;
        }
        R val = func_(a...);
        memo_.insert(std::make_pair(std::move(tup), val));
        return val;
    }

}; //end struct memoize_wrapper

Изменить: Пример использования:

Edit2: как указано, это не работает с рекурсивными функциями.

#include "utility/memoize_wrapper.hpp"
#include <memory>
#include <vector>
#include <algorithm>
#include <iostream>

long factorial(long i)
{
    long result = 1;
    long current = 2;
    while(current <= i) {
        result *= current;
        ++current;
    }
    return result;
}

int main()
{
    std::vector<int> arg {10, 9, 8, 7, 6, 10, 9, 8, 7, 6};
    std::transform(arg.begin(), arg.end(), arg.begin(), memoize_wrapper<long, long>(factorial));
    for(long i : arg) {
        std::cout << i << "\n";
    }
}

Answer 5

Ниже приведен (потокобезопасный) шаблон функции C++17, который действует как std::invoke но запоминает результат:

/**
 * @brief      Drop-in replacement for std::invoke which memoizes the return
 *             result.
 *
 * @param[in]  function  The function whose result needs to be cached
 * @param[in]  args      The function arguments
 *
 * @tparam     Function  The function type
 * @tparam     Args      The argument types
 *
 * @return     A value obtained either by evaluating the function, or by
 *             recalling it from a cache.
 *
 * @note       The function provided must not be a type-erase function object
 *             like a raw function pointer or std::function, because this
 *             function depends on the uniqueness of the Function template
 *             parameter. If you were to call invoke_memoized(f, a) and
 *             invoke_memoized(g, b) in the same translation unit, where f and g
 *             were function pointers of the same type, and a and b were
 *             arguments of the same type, you'd end up using the same cache for
 *             both functions f and g. A reasonable attempt is made to detect
 *             these misuse cases via static_assert.
 */
template<typename Function, typename... Args>
auto invoke_memoized(Function function, Args... args)
{
    using key_type   = std::tuple<Args...>;
    using value_type = std::invoke_result_t<Function, Args...>;

    static_assert(! std::is_same_v<Function, std::function<value_type(Args...)>>,
        "cannot memoize on std::function (use a lambda instead)");

    static_assert(! std::is_same_v<Function, value_type(*)(Args...)>,
        "cannot memoize on function pointer (use a lambda instead)");

    static std::mutex mutex;
    static std::map<key_type, value_type> cache;

    auto key  = std::tuple(args...);
    auto lock = std::lock_guard<std::mutex>(mutex);

    if (cache.count(key))
    {
        return cache[key];
    }
    return cache[key] = std::apply(function, key);
}

Вы можете использовать это так:

auto c = invoke_memoized(std::plus<>(), 1, 2.3);

Статический кеш поддерживается для каждой комбинации типов объекта функции и аргумента. Как указаноstd::functionа необработанные указатели на функции отклоняются, поскольку функции со стиранием типов могут перепутать свои кеши. Вы можете легко изменить эту функцию, чтобы наложить ограничения на размер кеша.