Funciones inmutables almacenadas en caché o precalculadas en C # / C ++

Question

Por " función inmutable " o " método inmutable " ;, me refiero a una función cuyo resultado nunca variará si le das los mismos argumentos.

Me gustaría saber si alguien conoce una solución más genérica o menos detallada cuando desea almacenar en caché los valores calculados previamente de una función inmutable.

Permítanme explicar lo que quiero decir con un simple ejemplo:

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

Notas:
- Agregué la etiqueta C ++ como solución en C ++ también me interesaría
- El concepto de & Quot; funciones inmutables & Quot; es común para los desarrolladores de bases de datos, ya que una función se puede definir como " inmutable " ;, o " inmutable dentro de una transacción " (esta es una buena manera de mejorar el rendimiento de las consultas).

Gracias de antemano

Answer 1

" Memoization " puede ser un término útil, aquí. Existen algunas bibliotecas de memorización (podría jurar que había una en boost , pero no puedo encuéntralo en este momento). Haciendo una búsqueda en la web para & Quot; memorizar & Quot; o " memorización " y su idioma de elección revelará algunos éxitos.

Aquí hay un artículo ordenado en Wikilibros: Optimización de C ++ / Técnicas de optimización general / Memoization

Answer 2

Bueno, el uso de un delegado como Func<T> puede hacer que sea más reutilizable sin requerir polimorfismo / herencia, pero no hay nada más " incorporado " 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

podrías intentar algo como esto:

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

Y luego úsalo de la siguiente manera:

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

La idea es crear una función que tome una función (diversión) como argumento y devuelva otra función. La función devuelta envuelve diversión y proporciona un mapa de parámetros de entrada de formulario (run_args) a los resultados. Por lo tanto, tiene la misma firma que diversión, se cansa de encontrar el resultado de los parámetros dados (run_args) en el mapa (caché). Luego devuelve el valor almacenado en caché o el resultado calculado por diversión. Obviamente, el resultado de la diversión debe agregarse a la memoria caché en caso de una búsqueda fallida.

Saludos

Jan

Answer 4

Puede hacerlo un poco menos detallado:

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

Otras notas sobre este tipo de patrón:

• Si usa C ++ y dicho método const, no será posible modificar miembros porque también se tratan como mutable en el contexto de ese método. Sin embargo, puede anular esto marcando los miembros que necesita modificar como <=>.
• Hay una diferencia entre " const semántica " y " bitwise const " ;. Cuando un autor marca algo como <=>, generalmente significa & Quot; semántica const & Quot; (que es lo que quiere decir en este caso), pero el compilador solo puede aplicar " bitwise const " ;.
Los métodos
• <=> generalmente le dan a la persona que llama la impresión de que pueden ser llamados desde múltiples hilos simultáneamente, ya que no tienen efectos secundarios. En este tipo de patrón tiene un & Quot; bitwise & Quot; efecto secundario, pero no & "; semántico &"; efecto secundario. Por lo tanto, si es posible que varios subprocesos puedan llamar a dicho método, debe proteger internamente esta inicialización.

Answer 5

Puede hacer que su miembro sea mutable (palabra clave).

Esto permitirá que una función miembro const modifique este valor. Lo uso todo el tiempo para almacenar en caché los resultados intermedios.

Answer 6

Puede reescribir este código casi al pie de la letra 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);
         }
     }
};

No estoy seguro de si una comprobación para ver si mComputeStuff_Cached está vacía () es suficiente. Podría ser que empty () sea un resultado legítimamente almacenado en caché.

Answer 7

Puede usar la palabra clave static dentro de la función. Se computará solo una vez:

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

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

Answer 8

Una solución C ++ sería muy similar a lo que usted ha descrito, y solo diferiría en la combinación embriagadora de const interfaces públicas calificadas y (algunos) miembros de mutable:

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