Quels types de fonctions sont candidats à la mémorisation?

Question

J'ai décidé sur PostSharp (indiscernable de la magie) pour lire les attributs et memoize functions. Le hachage de l'appel de fonction sera la clé et le résultat mis en cache (dans Velocity) sera renvoyé au lieu d'appeler à nouveau la fonction. Peasy facile, mac-and-cheesy.

J'ai déjà given up sur la possibilité de détecter des effets secondaires dans les fonctions décorées, ce qui s'est avéré être un "problème difficile", même pour les experts, ce que je ne suis certainement pas. Ensuite, je dois déterminer quelles autres fonctions sont candidates à la mémo. Qu'en est-il des méthodes qui prennent des types de référence complexes en tant que paramètres?

• Qu'en est-il des méthodes qui dépendent des données dans les instances à partir desquelles elles sont appelées?

Les objets de données ActiveRecord-esque viennent à l'esprit sur ce dernier. Est-ce que je vais devoir refactoriser un code d'une semaine pour prendre en charge la mémoisation?

Answer 1

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.

Answer 2

Eh bien, toute fonction, théoriquement, est un candidat pour la mémoisation. Cependant, rappelez-vous que la mémoisation concerne l'échange d'espace pour la vitesse -

En général, cela signifie que plus un état nécessite ou dépend d'une fonction pour calculer une réponse, plus le coût de l'espace est élevé, ce qui réduit la désirabilité Mémoize la méthode.

Vos deux exemples sont essentiellement des cas où plus d'état devrait être sauvegardé. Cela a deux effets secondaires. Tout d'abord, cela nécessitera beaucoup plus d'espace mémoire pour mémoriser la fonction, car plus d'informations devront être sauvegardées. Deuxièmement, cela ralentira potentiellement la fonction mémoized, car plus l'espace est grand, plus le coût de la recherche de la réponse est élevé, et plus le coût de trouver si un résultat a été précédemment enregistré est élevé.

En général, j'ai tendance à ne considérer que les fonctions qui ont peu d'entrées possibles et de faibles besoins de stockage, à moins que le calcul de la réponse ne coûte très cher. Je reconnais que cela est vague, mais cela fait partie du "art" de l'architecture. Il n'y a pas de «bonne» réponse sans implémenter les deux options (fonctions memozied et non-memoized), profilage et mesure.

Answer 3

Vous avez déjà pensé à un moyen de fournir une solution AOP pour fournir une mémoisation autour de la fonction Foo, alors que reste-t-il à savoir?

Oui, vous pouvez passer un objet de complexité arbitraire en tant que paramètre à une fonction mémo, tant qu'il est immuable, comme toutes les choses dont il dépend. Encore une fois, ce n'est pas du tout facile à découvrir statiquement pour le moment. Êtes-vous toujours attaché à l'idée que vous pouvez examiner le code de manière statique afin de conseiller vos utilisateurs sur la question "Est-ce une bonne idée d'appliquer la mémoisation à la fonction Foo?"

Si vous en faites l'un de vos besoins, vous vous joindrez à un effort de recherche mondial qui a duré de nombreuses années jusqu'à présent. Cela dépend de votre ambition, je suppose.