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

Question

Par " fonction immuable " ou " méthode immuable " ;, je veux dire 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 détaillée lorsque vous souhaitez mettre en cache les valeurs précalculées d'une fonction immuable.

Laissez-moi vous expliquer ce que je veux dire avec 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é le tag C ++ car une solution en C ++ m'intéresserait aussi.
- Le concept de & Quot; fonctions immuables & Quot; 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 les performances des requêtes).

Merci d'avance

Answer 1

" Mémoization " peut être un terme utile, ici. Il existe quelques bibliothèques de mémoization (je pourrais jurer qu'il en existait une dans boost , mais je ne peux pas trouvez le pour le moment). Effectuer une recherche Web sur & Quot; memoize & Quot; ou " memoization " et votre langue de choix révélera quelques succès.

Voici un article soigné dans Wikibooks: Optimisation des techniques d'optimisation C ++ / générales / Mémorisation

Answer 2

L’utilisation d’un délégué tel que Func<T> peut le rendre plus réutilisable sans nécessiter de polymorphisme / héritage - mais il n’ya 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 3

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 utilisez-le 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 une fonction qui prend une fonction (fun) en argument et retourne une autre une fonction. La fonction renvoyée rend fun et fournit les paramètres d’entrée de la carte (run_args) aux résultats. Donc, il a la même signature que fun, fatigue de trouver le résultat pour des paramètres donnés (run_args) dans la carte (cache). Ensuite, il retourne la valeur en cache ou le résultat calculé par fun. Évidemment, le résultat de fun doit être ajouté au cache en cas d'échec de la recherche.

Cordialement

Jan

Answer 4

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 remarques sur ce type de motif:

• Si vous utilisez C ++ et une telle méthode const, la modification de membres ne sera pas possible car ils sont également traités comme mutable dans le contexte de cette méthode. Cependant, vous pouvez le remplacer en indiquant le ou les membres à modifier comme <=>.
• Il y a une différence entre & "; Constante sémantique &"; et & "; bitwise const &" ;. Lorsqu'un auteur marque quelque chose comme <=>, cela signifie généralement & Quot; sémantique const & Quot; (ce que vous voulez dire dans ce cas), mais le compilateur ne peut appliquer que & "; bitwise const &";.
Les méthodes
• <=> donnent généralement à l'appelant l'impression qu'elles peuvent être appelées simultanément par plusieurs threads, car elles n'ont aucun effet secondaire. Dans ce type de motif, vous avez un & Quot; bitwise & Quot; effet secondaire, mais pas de " sémantique " effet secondaire. 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 5

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

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

Answer 6

Vous pouvez réécrire ce code presque intégralement 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 sais pas si vérifier si mComputeStuff_Cached est vide () est suffisant. Il se peut que empty () soit un résultat légitimement mis en cache.

Answer 7

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

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

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

Answer 8

Une solution C ++ ressemblerait beaucoup à ce que vous avez décrit, ne différant que par le mélange enivrant de const interfaces publiques qualifiées et de (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;
    }
    // ...
};