Écrire la fonction de mémoization universelle en C++11

un compact retournant 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;
        }
    };
}

dans C++14, on peut utiliser la déduction généralisée du type de déclaration pour éviter la déduction indirecte imposée par le retour de std::function .

ce qui rend tout à fait général, permettant de passer des objets de fonction arbitraire sans les envelopper dans std::function d'abord est laissé comme un exercice pour le lecteur.

la bonne façon de faire la mémoization en C++ est de mélanger le combinateur en Y.

votre fonction de base a besoin d'une modification. Au lieu de s'appeler directement elle-même, elle prend comme premier argument une référence à elle-même (ou une récursion std::function<Same_Signature> comme premier argument).

nous commençons par un Y-combinator . Puis nous ajoutons un cache sur le operator() et le renommons en memoizer , et lui donnons un fixe signature (pour la table).

la seule chose qui reste est d'écrire un tuple_hash<template<class...>class Hash> qui fait un hachage sur un tuple.

le type de la fonction qui peut être memoized est (((Args...)->R), Args...) -> R , ce qui rend le memoizer de type ( (((Args...) -> R), Args...) -> R ) -> ((Args...) -> R) . Il peut également être utile d'avoir un combinateur en Y pour produire une implémentation récursive "traditionnelle".

notez que si la fonction memoized modifie son args lors d'un appel, le memoizer cache le résultats dans le mauvais endroit.

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

live exemple avec un hard-codée en fonction de hachage basée sur la ce tant de poster .

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

bien que @KerrekSB ait posté un lien vers une autre réponse, je pensais que je jetterais aussi ma réponse dans le ring (c'est probablement un peu moins compliqué que la réponse liée, bien qu'en essence c'est très 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

modifier: 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";
    }
}

j'ai eu le même problème. J'ai créé une macro qui supporte aussi (avec une petite modification dans le code récursif) la récursion. Le voici:

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

l'usage est vraiment 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)

Voir en action: http://ideone.com/C3JEUT :)