Funzione fattoriale memorizzata e ricorsiva?

Question

So come fare la memoizzazione in Python facilmente, ma ho bisogno di un modo più veloce per calcolarli, quindi sto usando C++. Tuttavia, non ho idea di come memoize. Capisco che si tratta di memorizzare i valori in una matrice o vettore e quindi di cercare il suo valore durante il recupero, ma sarebbe davvero utile vedere come questo è fatto in modo da poter provare la sua velocità.

Answer 1

Bene, il modo migliore che riesco a pensare di fare in C++ è probabilmente l'utilizzo di un oggetto funzione per memorizzare i valori memorizzati. Immagino che questo sia probabilmente un po 'simile al tuo decoratore python, anche se non ho mai veramente fatto alcun pitone. Il codice dovrebbe essere simile a questa:

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

Il codice definisce una classe modello che prende in un TypeName e un puntatore a funzione, l'operatore di funzione viene quindi definita sulla classe permettendo così di essere chiamato. L'operatore della funzione accetta un valore di input per verificare se tale valore si trova in una mappa, quindi o semplicemente lo restituisce dalla mappa o lo calcola (utilizzando il puntatore della funzione), lo aggiunge alla mappa e quindi lo restituisce.

Quindi supponendo che si definisce alcune funzioni di elaborazione come dire:

int unity(int in) { return in; } 

si può usare il codice come questo:

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

Così definiamo un'istanza della classe mem, che prende il nostro tipo di valore e la funzione di elaborazione come parametri del modello, quindi chiama semplicemente questa classe come una funzione.

Answer 2

Nessuno, tranne uno studente che apprende la ricorsione, calcolerebbe i fattoriali in questo modo.

La memorizzazione è un'ottima idea, soprattutto se si intende chiamare ripetutamente il metodo. Perché buttare via un buon lavoro?

Un'altra considerazione è un modo migliore per calcolare i fattoriali: utilizzare il registro naturale della funzione gamma. Manterrà l'overflow più a lungo, perché si restituisce un doppio valore. Il registro naturale crescerà più lentamente del valore. Se stai calcolando le combinazioni, il registro naturale modifica la moltiplicazione e la divisione in addizione e sottrazione.

Ma, con tutti i mezzi, memoize per qualsiasi implementazione che si utilizza. Se lo scrivi in ​​C++, ti consigliamo di utilizzare lo std:map con l'argomento x come chiave e il valore ln(gamma(x)).

Scusate, è passato troppo tempo da quando ho scritto C++ e STL. Preferirei usare una mappa hash con O(1) tempo di accesso in lettura per dover eseguire un'iterazione sui tasti in O(n).

Answer 3

Solo per divertimento, ecco un piccolo memoizer generico che ho scritto qualche tempo fa. Si richiede modelli 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); 
} 

io non sono del tutto sicuro se ho avuto il diritto rvalue-forwardiness, in quanto è molto tempo fa, che ho scritto questo. Comunque, ecco un banco di prova:

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

mi piace fare affidamento sulla cattura lambda come in (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]; 
    }); 
}