Написание универсальной функции запоминания в C ++ 11
Ищете способ реализовать универсальную универсальную функцию запоминания, которая возьмет функцию и вернет запомненную версию?
Ищите что-то вроде @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?
Решение
Компактный, возвращающий лямбду:
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 Первый оставлен в качестве упражнения для читателя.
Другие решения
Правильный способ запоминания в 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);
}
);
Хотя @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";
}
}
Я боролся с той же проблемой. Я создал макрос, который также поддерживает (с небольшими изменениями в рекурсивном коде) рекурсию. Вот:
#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 🙂