¿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; template class 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
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
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 🙂