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

c++11 memoization

Question

¿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 expresar decoradores genéricos y reutilizables en C ++, posiblemente usando las nuevas características de C ++ 11?

Answer 1

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 <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

Editar: uso de ejemplo:

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

#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 2

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<Same_Signature> 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_hash<template<class...>class 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 {};

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)}; }

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

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

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

#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;                                      /
    }                                                       /
}                                                           

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 :)

Answer 4

Una compacta que devuelve una lambda:

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;
        }
    };
}

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.