Ecriture de la fonction de mémorisation universelle en C ++11

Question

Vous cherchez un moyen d'implémenter une fonction de mémorisation générique universelle qui prendra une fonction et renverra la version mémoisée de la même chose?

Vous recherchez quelque chose comme décorateur en python @memo (du site de Norving).

 def memo(f):
    table = {}
    def fmemo(*args):
        if args not in table:
            table[args] = f(*args)
        return table[args]
    fmemo.memo = table
    return fmemo
 

Plus généralement, existe-t-il un moyen d’exprimer des décorateurs génériques et réutilisables en C ++, en utilisant éventuellement les nouvelles fonctionnalités de C ++ 11?

Answer 1

Un compact qui retourne un 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, on peut utiliser la déduction de type de retour généralisé pour éviter l'indirection supplémentaire imposée par le retour de std::function .

En généralisant ceci, permettre de passer des objets de fonction arbitraires sans les envelopper dans std::function premier reste un exercice pour le lecteur.

Answer 2

Bien que @KerrekSB ait posté un lien vers une autre réponse, je me suis dit que je mettrais également ma réponse dans le ring (elle est probablement un peu moins compliquée que la réponse associée, bien que ce soit essentiellement similaire):

 #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
 

Edit: Exemple d'utilisation:

Edit2: Comme indiqué, cela ne fonctionne pas avec les fonctions récursives.

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