Que tipos de funções são candidatos para memoization?

Question

Eu decidi sobre PostSharp (indistinguível da magia) para ler atributos e Memoize funções . O hash da chamada de função será a chave eo cache (em Velocity ) resultado será retornado em vez de chamar a função novamente. Fácil peasy, mac-e-queijo.

Eu tenho dado já -se de ser capaz de detectar efeitos colaterais em funções decorados, que acabou por ser um "problema difícil", mesmo para os especialistas, o que eu certamente não estou. Em seguida, eu tenho que descobrir o que outras funções são candidatos para memoization.

• O que sobre os métodos que levam tipos de referência complexos como parâmetros?
• O que sobre os métodos que dependem dentro de dados dos casos, eles são chamados de?

objetos de dados ActiveRecord-esque vêm à mente naquele último.

Am I vai ter que código semanas de idade refactor para memoization suporte?

Answer 1

Você só pode memoize uma função, se todas as suas entradas são tipos de valor ou tipos de referência imutáveis, se ele retorna um tipo de valor ou uma nova instância de um tipo de referência, e se ele não tem efeitos colaterais. Período.

Memoização depende de um mapeamento determinista entre entradas e saídas. Cada chamada para F(a, b, c) em que a, b, ec conter os mesmos valores devem retornar o mesmo resultado para que memoization ser possível.

Se um parâmetro é um tipo de referência, então, mesmo que o seu valor não muda, várias chamadas para a função usando pode produzir um resultado diferente. Um exemplo trivial:

public int MyFunction(MyType t)
{
   return t.Value;
}

Console.WriteLine(MyFunction(t));
t.Value++;
Console.WriteLine(MyFunction(t));

Da mesma forma, se uma função depende de um valor externo a ele, em seguida, várias chamadas para essa função com os mesmos parâmetros podem retornar resultados diferentes:

int Value = 0;

public int MyFunction(int input)
{
   return Value;
}

Console.WriteLine(MyFunction(1));
Value++;
Console.WriteLine(MyFunction(1));

E céu ajudá-lo se a sua função memoized faz outra coisa que não retorna um valor ou um novo tipo de referência:

int Value = 0;

public int MyFunction(int input)
{
   Value++;
   return input;
}

Se você chamar essa função 10 vezes, Value será de 10. Se você refatorar-lo para usar memoization e então chamá-lo 10 vezes, Value será 1.

Você pode começar a descer o caminho de descobrir como memoize estado, de modo que você pode falso de uma função que memoizes um tipo de referência. Mas o que você está realmente memoizing é o conjunto de valores que a função funciona em. Você pode semelhante cortar uma função memoized que tem efeitos colaterais para que os seus efeitos secundários ocorrer antes do memoization. Mas tudo isso é pedindo para ter problemas.

Se você quiser implementar memoization para uma função que leva um tipo de referência, a abordagem adequada é refatorar fora a parte da função que só funciona em tipos de valor, e memoize essa função, por exemplo:.

public int MyFunction(MyType t)
{
   return t.Value + 1;
}

a esta:

public int MyFunction(MyType t)
{
   return MyMemoizableFunction(t.Value);
}

private int MyMemoizableFunction(int value)
{
   return value + 1;
}

Qualquer outra abordagem para memoization implementação que você tome qualquer um) faz a mesma coisa, através de meios mais obscuros, ou b) não vai funcionar.

Answer 2

Bem, qualquer função, teoricamente, é um candidato para memoization. No entanto, lembre-se que memoization é tudo sobre negociação de espaço para a velocidade -

De uma maneira geral, isto significa que, o estado mais uma função requer ou depende da, a fim de calcular a resposta, quanto maior o custo de espaço, o que reduz a oportunidade para memoize o método.

Ambos os exemplos são basicamente casos em que mais estado precisariam ser salvos. Isto tem dois efeitos colaterais.

Em primeiro lugar, isso vai exigir muito mais espaço de memória, a fim de memoize a função, uma vez que mais informação terá de ser salva.

Em segundo lugar, isso vai potencialmente abrandar a função memoized, já que quanto maior o espaço, maior o custo da pesquisa da resposta, bem como quanto maior o custo em encontrar ou não resultado foi salvo anteriormente.

Em geral, eu tendem a considerar apenas funções que têm poucas entradas possíveis e baixos requisitos de armazenamento, a menos que haja um custo muito elevado no cálculo da resposta.

Eu acknoledge que este é vago, mas isso é parte da "arte" na arquitetura. Não há nenhuma resposta "certa" sem implementar ambas as opções (memozied e funções não memoized), de perfil, e medir.

Answer 3

Você já pensou em uma maneira de fornecer uma solução AOP para fornecer memoization torno função Foo, então o que é deixado para descobrir?

Sim, você pode passar um objeto de complexidade arbitrária como um parâmetro para uma função memoized, contanto que é imutável, como são todas as coisas que ele dependa. Novamente, isto não é nada fácil para descobrir estaticamente no momento.

Você ainda está casado com a idéia de que você pode estaticamente examinar o código, a fim de aconselhar os seus usuários sobre a questão "É uma boa idéia para aplicar memoization a função Foo?"

Se você fizer que uma das suas necessidades, você vai se juntar a um esforço global de pesquisa que durou muitos anos até agora. Depende de como você é ambicioso, eu acho.