Fonctions immuables en cache ou précalculées en C#/C++

Question

Par "fonction immuable" ou "méthode immuable", j'entends une fonction dont le résultat ne variera jamais si vous lui donnez les mêmes arguments.

Je serais intéressé de savoir si quelqu'un connaît une solution plus générique ou moins verbeuse lorsque vous voulez mettre en cache les valeurs précalculées d'une fonction immuable.

Laissez-moi vous expliquer ce que je veux dire par un exemple simple:

//Let's assume that ComputeStuff() returns a widely used value 
//and that 
//1. It is immutable (it will always return the same result) 
//2. its performance is critical, and it cannot be accepted to compute 
// the result at each call, because the computation is too slow 
//I show here a way to solve the problem, based on a cached result. 
//(this example works in a case of a method with no arguments. 
// A hash would be required in order to store multiple precomputed results 
//depending upon the arguments) 
private string mComputeStuff_Cached = null; 
public string ComputeStuff() 
{ 
    if (mComputeStuff_Cached != null) 
    return mComputeStuff_Cached ; 

    string result; 
    // 
    // ... 
    //Do lots of cpu intensive computation in order to compute "result" 
    //or whatever you want to compute 
    //(for example the hash of a long file) 
    //... 
    // 

    mComputeStuff_Cached = result; 
    return mComputeStuff_Cached ; 
} 

Notes:
- J'ai ajouté la balise C++ comme une solution en C++ serait aussi me intéresser
- Le concept de « fonctions immuables "est commun aux développeurs de bases de données, puisqu'une fonction peut être définie comme" immuable ", ou" immuable dans une transaction "(c'est un bon moyen d'améliorer la performance des requêtes).

Merci à l'avance

Answer 1

"Memoization" peut être un terme utile, ici. Il y a quelques bibliothèques de mémoisation là-bas (je pourrais jurer qu'il y en avait une en boost, mais je ne peux pas le trouver pour le moment).Faire une recherche sur le Web pour "mémoize" ou "mémoization" et votre langue de choix révélera quelques hits.

est ici un article propre à Wikibooks: Optimizing C++/General optimization techniques/Memoization

Answer 2

Une solution C++ serait très similaire à ce que vous avez décrit, qui ne diffèrent que dans le mélange enivrant de const public interface qualifié (s) et (certains) mutable membres:

class Computer { 
    mutable string cache; 
    public: 
    // I wouldn't call it ComputeXXX 
    // since I want to hide the implementation 
    // details from my client: for the client 
    // there is no change in state due to a call 
    // to this function 
    const string& StringVal() const { 
     if (cache.empty()) { 
       // compute cache 
     } 
     return cache; 
    } 
    // ... 
};    

Answer 3

Vous pouvez le rendre un peu moins bavard:

private string mComputeStuff_Cached = null; 
public string ComputeStuff() 
{ 
    if (mComputeStuff_Cached == null) { 
    string result; 
    // 
    // ... 
    //Do lots of cpu intensive computation in order to compute "result" 
    //or whatever you want to compute 
    //(for example the hash of a long file) 
    //... 
    // 

    mComputeStuff_Cached = result; 
    } 

    return mComputeStuff_Cached ; 
} 

Autres notes sur ce type de modèle:

• Si vous utilisez C++, et un tel procédé const, puis les membres modification ne sera pas possible, car ils sont également traités comme const dans le cadre de cette méthode. Cependant, vous pouvez le remplacer en marquant les membres que vous devez modifier comme mutable.
• Il existe une différence entre "const sémantique" et "const bitwise". Quand un auteur marque quelque chose comme const, ils signifient généralement "const sémantique" (ce que vous voulez dire dans ce cas), mais le compilateur peut seulement appliquer "bitwise const".
• const méthodes donnent généralement à l'appelant l'impression qu'ils peuvent être appelés à partir de plusieurs threads simultanément, car ils n'ont pas d'effets secondaires. Dans ce type de modèle, vous avez un effet secondaire «au niveau du bit», mais pas d'effet secondaire «sémantique». Par conséquent, s'il est possible que plusieurs threads puissent appeler une telle méthode, vous devez protéger cette initialisation en interne.

Answer 4

Vous pouvez rendre votre variable membre mutable (mot-clé).

Cela permettra à une fonction membre const de modifier cette valeur. Je l'utilise tout le temps pour mettre en cache les résultats intermédiaires.

Answer 5

Vous pouvez réécrire ce code presque mot pour mot en C++

class CClass 
{ 

    private: 
    std::string* mComputeStuff_Cached; 

    public: 
    CClass() 
     mComputeStuff_Cached(NULL) 
    { 

    } 

    ~CClass() 
    { 
      delete mComputeStuff_Cached; 
    } 


    std::string ComputeStuff() 
    { 
     if (mComputeStuff_Cached != NULL) 
     { 
      return mComputeStuff_Cached 
     } 
     else 
     { 
      std::string calcedAnswer; 
      ... 
      // store away answer 
      mComputeStuff_Cached = new std::string(calcedAnswer); 
     } 
    } 
}; 

Je ne suis pas sûr si un chèque pour voir si mComputeStuff_Cached est vide() est suffisante. Il se pourrait que empty() soit un résultat légitimement mis en cache.

Answer 6

Eh bien, en utilisant un délégué tel que Func<T> peut le rendre plus réutilisable sans nécessiter polymorphisme/héritage - mais il n'y a rien de plus « intégré » en C#:

using System; 
static class Program { 
    static void Main() { 
     var func = CachedFunc.Create(() => int.Parse(Console.ReadLine())); 

     Console.WriteLine(func.Value); 
     Console.WriteLine(func.Value); 
    } 
} 
static class CachedFunc { 
    public static CachedFunc<T> Create<T>(Func<T> func) { 
     return new CachedFunc<T>(func); 
    } 
} 
class CachedFunc<T> { 
    T value; 
    Func<T> func; 
    public CachedFunc(Func<T> func){ 
     if (func == null) throw new ArgumentNullException("func"); 
     this.func = func; 
    } 
    public T Value { 
     get { 
      if (func != null) { 
       value = func(); 
       func = null; 
      } 
      return value; 
     } 
    } 
    public static explicit operator T(CachedFunc<T> func) { 
     return func.Value; } 
} 

Answer 7

Vous pouvez utiliser le mot-clé static dans la fonction. Il sera calculé qu'une seule fois:

std::string GetWidelyUsedValue() 
{ 
    static std::string value = ComputeStuff() ; 
    return value ; 
} 

std::string ComputeStuff() 
{ 
    // Compute the string here. 
} 

Answer 8

vous pouvez essayer quelque chose comme ceci:

#include <functional> 
#include <type_traits> 
#include <map> 
#include <tuple> 

//requires c++14 
auto add_function_cache = [](auto fun) { 
    using fun_type = decltype(fun); 
    return ([=](auto... run_args){ 
     using fun_return_type = std::result_of_t<fun_type(decltype(run_args)...)>; 
     static std::map< 
      std::tuple<decltype(run_args)...>, 
      fun_return_type 
     > result_cache; 
     std::tuple<decltype(run_args)...> tuple(run_args...); 
     if (result_cache.find(tuple) == result_cache.end()) { 
      fun_return_type rv = fun(run_args...); 
      result_cache[tuple] = rv; 
      return rv; 
     } 
     else { 
      return result_cache[tuple]; 
     } 
    }); 
}; 

template <typename R, class... Args> auto 
add_function_cache_old(std::function<R(Args...)> fun) 
-> std::function<R(Args...)> 
{ 
    std::map<std::tuple<Args...>, R> cache; 
    return [=](Args... args) mutable { 
     std::tuple<Args...> t(args...); 
     if (cache.find(t) == cache.end()) { 
      R rv = fun(args...); 
      cache[t] = rv; 
      return rv; 
     } 
     else { 
      return cache[t]; 
     } 
    }; 
}; 

Et puis utilisez comme suit:

//function_cache - usage 
auto fib_cache = add_function_cache(&fib); 

//function_cache_old - usage 
function<decltype(fib)> fib_fn = &fib; 
auto fib_cache_old = add_function_cache_old(fib_fn); 

fib_cache(10); 
fib_cache(10); 

L'idée est de créer un fonction qui prend une fonction (fun) en argument et renvoie une autre fonction . La fonction retournée s'amuse et fournit des paramètres d'entrée de forme de carte (run_args) aux résultats. Donc, il a la même signature que fun, les pneus pour trouver le résultat des paramètres donnés (run_args) dans la carte (cache). Ensuite, il retourne la valeur mise en cache ou le résultat calculé par plaisir. Il est évident que le résultat du fun doit être ajouté au cache en cas de recherche infructueuse.

Cordialement

Jan