Vous ne pouvez mémoriser une fonction que si toutes ses entrées sont des types de valeur ou des types de référence immuables, si elle retourne un type de valeur ou une nouvelle instance d'un type de référence et si elle n'a pas d'effets secondaires. Période. La mémorisation dépend d'un mappage déterministe entre les entrées et les sorties. Tout appel à F(a, b, c) dans lequel a, b et c contiennent les mêmes valeurs doit renvoyer le même résultat pour que la mémorisation soit possible.
Si un paramètre est un type de référence, alors même si sa valeur ne change pas, plusieurs appels à la fonction qui l'utilisent peuvent produire un résultat différent.Un exemple trivial:
public int MyFunction(MyType t)
{
return t.Value;
}
Console.WriteLine(MyFunction(t));
t.Value++;
Console.WriteLine(MyFunction(t));
De même, si une fonction dépend d'une valeur externe à elle, puis plusieurs appels à cette fonction avec les mêmes paramètres peuvent retourner des résultats différents:
int Value = 0;
public int MyFunction(int input)
{
return Value;
}
Console.WriteLine(MyFunction(1));
Value++;
Console.WriteLine(MyFunction(1));
Et le ciel vous aide si votre fonction memoized fait autre chose que de retourner une valeur ou un nouveau type de référence:
int Value = 0;
public int MyFunction(int input)
{
Value++;
return input;
}
Si vous appelez cette fonction 10 fois, Value sera 10. Si vous le reformulez pour utiliser la mémorisation et que vous l'appelez 10 fois, Value sera égal à 1.
Vous pouvez commencer à déterminer comment mémoriser l'état, de sorte que vous puissiez fonction qui mémorise un type de référence. Mais ce que vous êtes vraiment en train de mémoriser, c'est l'ensemble des valeurs sur lesquelles la fonction fonctionne. Vous pouvez également pirater une fonction mémo qui a des effets secondaires afin que ses effets secondaires se produisent avant la mémo. Mais tout cela demande des ennuis.
Si vous souhaitez implémenter memoization dans une fonction qui prend un type de référence, la bonne approche est de factoriser la partie de la fonction qui ne fonctionne que sur les types de valeur et memoize cette fonction, par exemple:
public int MyFunction(MyType t)
{
return t.Value + 1;
}
à ceci:
public int MyFunction(MyType t)
{
return MyMemoizableFunction(t.Value);
}
private int MyMemoizableFunction(int value)
{
return value + 1;
}
Toute autre approche de la mise en œuvre memoization que vous prenez soit a) fait la même chose, par des moyens plus obscurs, ou b) ne fonctionnera pas.
Vous devrez certainement refactoriser mon cerveau pour le soutenir - quelle est la mémo? –
http://en.wikipedia.org/wiki/Memoization - Éviter les recalculs dans les fonctions pour la même entrée. –
Je suis venu ici pour éditer la question, pensant que c'était une faute de frappe .... – womp