Funções imutáveis ??em cache ou pré-computadas em C # / C ++

Question

Por "função imutável" ou "método imutável", quero dizer uma função cujo resultado nunca irá variar se você dar-lhe os mesmos argumentos.

Eu estaria interessado em saber se alguém sabe de uma forma mais genérica ou menos detalhada solução quando você deseja armazenar em cache o valor pré-computado (s) de uma função imutável.

Deixe-me explicar o que quero dizer com um exemplo simples:

//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:
- Eu adicionei a tag C ++ como uma solução em C ++ também me interessa
- O conceito de "funções imutáveis" é comum para os desenvolvedores de banco de dados, uma vez que uma função pode ser definida como "imutável", ou "imutável dentro de uma transação" (esta é uma boa maneira de melhorar o desempenho das consultas)

Agradecemos antecipadamente

Answer 1

" Memoização " pode ser um termo útil, aqui. Existem algumas bibliotecas memoização lá fora (eu poderia jurar que havia uma em impulso , mas não posso encontrá-lo no momento). Fazendo uma pesquisa na web para "memoize" ou "memoization" e idioma de sua escolha irá revelar alguns hits.

Aqui está um artigo puro em Wikibooks: técnicas Otimizando C ++ / otimização Geral / Memoização

Answer 2

Bem, usando um delegado como Func<T> pode torná-lo mais re-utilizáveis ??sem exigir polimorfismo / herança - mas não há nada mais "embutido" em 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

você poderia tentar algo como isto:

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

E, em seguida, usá-lo da seguinte forma:

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

A idéia é criar uma função que leva uma função (diversão) como argumento e retorna outra função. A função retornou envolve diversão e fornece um mapa parâmetros de entrada de formulário (run_args) para resultados. Por isso, tem a mesma assinatura como diversão, pneus para encontrar o resultado para determinados parâmetros (run_args) no mapa (cache). Em seguida, ele retorna o valor em cache ou o resultado calculado pela diversão. Obviamente o resultado de diversão tem que ser adicionado ao cache no caso de um look-up sem sucesso.

Saudações

Jan

Answer 4

Você pode torná-lo um pouco menos detalhada:

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

Outras notas sobre este tipo de padrão:

• Se você usar C ++, e tal const método, em seguida, os membros modificando não será possível, porque eles também são tratados como const dentro do contexto desse método. No entanto, você pode substituir esse marcando os membros (s) que você precisa para modificar como mutable.
• Há uma diferença entre "const semântica" e "const bit a bit". Quando um marcas autor algo tão const, eles geralmente média "const semântica" (que é o que você quer dizer neste caso), mas o compilador só pode impor "bit a bit const".
• métodos const costumam dar o chamador a impressão de que eles podem ser chamados a partir de múltiplas threads simultaneamente, porque eles não têm efeitos colaterais. Neste tipo de padrão que você tem um efeito colateral "bit a bit", mas nenhum efeito colateral "semântica". Portanto, se é possível que vários segmentos poderia chamar esse método você deve proteger internamente essa inicialização.

Answer 5

Você pode fazer seu variável mutável membro (palavra-chave).

Isso permitirá uma função membro const modificar este valor. Eu usá-lo o tempo todo para os resultados intermediários de cache.

Answer 6

Você pode reescrever este código quase literalmente em 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);
         }
     }
};

Eu não tenho certeza se uma verificação para ver se mComputeStuff_Cached é empty () é suficiente. Pode ser que empty () é um resultado legitimamente em cache.

Answer 7

Você pode usar a palavra-chave static dentro da função. Ele será calculado apenas uma vez:

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

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

Answer 8

solução A C ++ seria muito semelhante ao que você tem delineado, diferindo apenas na mistura inebriante de const qualificado interface pública (s) e (alguns) membros 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;
    }
    // ...
};