¿Función factorial recursiva y memorizada?

Question

Sé cómo hacer memoria en Python fácilmente, pero necesito una forma más rápida de calcularlos, así que estoy usando C++. Sin embargo, no tengo idea de cómo memorizar. Entiendo que se trata de almacenar valores en una matriz o vector y luego buscar su valor al recuperarlos, pero sería muy útil ver cómo se hace para poder probar su velocidad.

Answer 1

Bueno, la mejor forma que se me ocurre para hacer esto en C++ probablemente sea utilizando un objeto de función para almacenar los valores memorizados. Supongo que esto es probablemente un poco similar a tu decorador de pitones, aunque nunca he hecho ningún pitón. El código sería algo como esto:

template <typename T, T (*calc)(T)> 
class mem { 
    std::map<T,T> mem_map; 

public: 
    T operator()(T input) { 
    typename std::map<T,T>::iterator it; 

    it = mem_map.find(input); 
    if (it != mem_map.end()) { 
     return it->second; 
    } else { 
     T output = calc(input); 
     mem_map[input] = output; 
     return output; 
    } 
    } 
}; 

El código define una clase de plantilla que se lleva en un nombre de tipo y un puntero de función, el operador de la función se define a continuación en la clase que le permite ser llamado. El operador de función toma un valor de entrada que verifica si dicho valor está en un mapa, luego simplemente lo devuelve del mapa o lo calcula (usando el puntero de función), lo agrega al mapa y luego lo devuelve.

Así que asumiendo que defina una función de procesamiento, como por ejemplo:

int unity(int in) { return in; } 

debe utilizar el código como el siguiente:

mem<int, unity> mem_unity; 
int y; 
y = mem_unity(10); 

Así que definen una instancia de la clase mem que tiene nuestro tipo de valor y la función de procesamiento como parámetros de plantilla, luego simplemente llame a esta clase como una función.

Answer 2

Nadie, excepto un alumno que aprenda recursividad, calcularía los factores de esa manera.

La memorización es una muy buena idea, especialmente si va a llamar al método repetidamente. ¿Por qué tirar el buen trabajo?

Otra consideración es una mejor manera de calcular factoriales: utilice el registro natural de la función gamma. Resistirá al desbordamiento por más tiempo, porque devuelve un doble valor. El registro natural crecerá más lentamente que el valor. Si está calculando combinaciones, el registro natural cambia la multiplicación y la división en suma y resta.

Pero, por supuesto, memoize para cualquier implementación que utilice. Si lo está escribiendo en C++, le recomendaría usar un std:map con el argumento x como clave y el ln(gamma(x)) como valor.

Lo siento, ha pasado demasiado tiempo desde que escribí C++ y STL. Prefiero usar un mapa hash con O(1) tiempo de acceso de lectura para tener que iterar sobre las claves en O(n).

Answer 3

Solo por diversión, aquí hay un pequeño memomario genérico que escribí hace algún tiempo. Se requiere plantillas variadic, naturalmente:

template <template <typename...> class Container, typename...> struct Memo; 

template <typename R, typename... Args, template <typename...> class Container> 
struct Memo<Container, R, std::tuple<Args...>> 
{ 
    Memo(std::function<R(Args...)> f) : func(f) { } 

    R operator()(Args && ...args) 
    { 
    const auto arg = std::make_tuple(args...); 
    typename CacheContainer::const_iterator it = cache.find(arg); 

    if (it == cache.cend()) 
    { 
     it = cache.insert(typename CacheContainer::value_type(arg, func(std::forward<Args>(args)...))).first; 
     std::cout << "New call, memoizing..." << std::endl; 
    } 
    else 
    { 
     std::cout << "Found it in the cache!" << std::endl; 
    } 

    return it->second; 
    } 

private: 

    typedef Container<typename std::tuple<Args...>, R> CacheContainer; 

    std::function<R(Args...)> func; 
    CacheContainer cache; 
}; 


template <typename R, typename... Args> 
Memo<std::map, R, std::tuple<Args...>> OMapMemoize(R(&f)(Args...)) 
{ 
    return Memo<std::map, R, std::tuple<Args...>>(f); 
} 
template <typename R, typename... Args> 
Memo<std::unordered_map, R, std::tuple<Args...>> UMapMemoize(R(&f)(Args...)) 
{ 
    return Memo<std::unordered_map, R, std::tuple<Args...>>(f); 
} 

No estoy del todo seguro de si tenía derecho rvalue-forwardiness, ya que es hace mucho tiempo que escribí esto. De todos modos, aquí hay un caso de prueba:

int foo(double, char) { return 5; } 

int main() 
{ 
    auto f = OMapMemoize(foo); 
    auto g = UMapMemoize(foo); 

    int a, b; 

    a = f(1.0, 'a'); 
    a = f(1.0, 'a'); 
    a = f(1.0, 'a'); 
    a = f(1.0, 'a'); 

    b = g(1.0, 'a'); 
    b = g(1.0, 'a'); 
    b = g(1.0, 'a'); 
    b = g(1.0, 'a'); 

    return a; 
} 

Answer 4

me gusta depender de captura lambda como en (usa std=c++14)

template<typename R, typename... Args> 
auto memoize(std::function<R(Args...)>&& f) 
{ 
    using F = std::function<R(Args...)>; 
    std::map<std::tuple<Args...>,R> cache; 
    return ([cache = std::map<std::tuple<Args...>,R>{}, 
      f = std::forward<F>(f)](Args&&... args) mutable 
    { 
     std::tuple<Args...> t(args...); 
     if (cache.find(t) == cache.end()) 
     { 
      R r = f(std::forward<Args...>(args)...); 
      cache[t] = r; 
     } 
     return cache[t]; 
    }); 
}