Escribir la función de memoria universal en C ++ 11

¿Busca una forma de implementar una función universal de memoria genérica que tome una función y devuelva la versión memorada de la misma?

Buscando algo así como @memo (del sitio de Norving) decorador en 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

Yendo más general, ¿hay alguna manera de express decoradores generics y reutilizables en C ++, posiblemente usando las nuevas características de C ++ 11?

Una compacta que devuelve una lambda:

 template  std::function memo(R (*fn)(Args...)) { std::map, 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; } }; }

En C ++ 14, se puede utilizar la deducción del tipo de retorno generalizado para evitar la indirección adicional impuesta al devolver std::function .

Haciendo esto completamente general, permitiendo pasar objetos de funciones arbitrarias sin envolverlos en std::function primero se deja como un ejercicio para el lector.

La forma correcta de hacer memoizations en C ++ es mezclar el Y-combinator en.

Su función base necesita una modificación. En lugar de llamarse a sí mismo directamente, toma una referencia de plantilla a sí misma como su primer argumento (o, una recursión de std::function como su primer argumento).

Comenzamos con un Y-combinator . Luego agregamos un caché en el operator() y le memoizer nombre a memoizer , y le damos una firma fija (para la tabla).

Lo único que queda es escribir un tuple_hashclass Hash> que haga un hash en una tupla.

El tipo de función que se puede memorizar es (((Args...)->R), Args...) -> R , lo que hace que el memo de tipo ( (((Args...) -> R), Args...) -> R ) -> ((Args...) -> R) . Tener un combinador en Y para producir una implementación recursiva “tradicional” también puede ser útil.

Tenga en cuenta que si la función memorizada modifica sus argumentos durante una llamada, el memoizer guardará los resultados en el lugar equivocado.

 struct wrap {}; templateclass Hash=std::hash> struct memoizer; templateclass Hash> struct memoizer { using base_type = F; private: F base; std::unordered_map< std::tuple...>, R, tuple_hash > cache; public: template 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)...); cache.emplace( std::move(args), retval ); return decltype(retval)(retval); } template 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)...); 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 memoizer( wrap, L&& f ): base( std::forward(f) ) {} }; template memoizer> memoize( F&& f ) { return {wrap{}, std::forward(f)}; }

ejemplo en vivo con una función hash codificada basada en esta publicación SO .

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

Aunque @KerrekSB publicó un enlace a otra respuesta, pensé que también lanzaría mi respuesta al ring (probablemente sea un poco menos complicado que la respuesta vinculada, aunque en esencia es muy similar):

 #include  #include  #include  #include  /*! \brief A template functor class that can be utilized to memoize any * given function taking any number of arguments. */ template  struct memoize_wrapper { private: std::map, R> memo_; std::function func_; public: /*! \brief Auto memoization constructor. * * \param func an the std::function to be memoized. */ memoize_wrapper(std::function 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(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

Editar: uso de ejemplo:

Edit2: Como se señaló, esto no funciona con funciones recursivas.

 #include "utility/memoize_wrapper.hpp" #include  #include  #include  #include  long factorial(long i) { long result = 1; long current = 2; while(current <= i) { result *= current; ++current; } return result; } int main() { std::vector arg {10, 9, 8, 7, 6, 10, 9, 8, 7, 6}; std::transform(arg.begin(), arg.end(), arg.begin(), memoize_wrapper(factorial)); for(long i : arg) { std::cout << i << "\n"; } }

Luché con el mismo problema. Creé macro que también admite (con pequeñas modificaciones en el código recursivo) recursividad. Aquí está:

 #include  #include  #define MEMOIZATOR(N, R, ...) \ R _ ## N (__VA_ARGS__); \ std::map, R> _memo_ ## N; \ template  \ RN (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; \ } \ }

El uso es realmente simple:

 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)

Véalo en acción: http://ideone.com/C3JEUT 🙂

Intereting Posts

Mover GameObject a lo largo del tiempo Combina bibliotecas estáticas ¿Cómo resuelve la herencia virtual la ambigüedad “diamante” (herencia múltiple)?Cómo representar el número de FLOAT en la memoria en C Función que se devuelve “Primitiva JSON inválida” en el procesamiento de Ajax C leer el código binario ¿Qué son los funtores de C ++ y sus usos?