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

Question

J'ai décidé d'utiliser PostSharp (indiscernable de la magie) pour lire les attributs et les fonctions memoize . . Le hachage de l'appel de fonction sera la clé et le caché (dans Velocity ) result sera retourné au lieu de rappeler la fonction. Peasy facile, mac-and-fromage.

J'ai déjà donné up sur la possibilité de détecter des effets secondaires dans des 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émorisation.

• 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 à l'intérieur des 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 renvoie un type de valeur ou une nouvelle instance d'un type de référence et si elle n'a aucun effet secondaire. Période.

La mémorisation dépend d’un mappage déterministe entre les entrées et les sorties. Chaque 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, même si sa valeur ne change pas, plusieurs appels à la fonction qui l'utilise 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 à celle-ci, plusieurs appels à cette fonction avec les mêmes paramètres peuvent renvoyer 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 que Dieu vous aide si votre fonction mémoize fait autre chose que renvoyer 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, Valeur sera 10. Si vous la refactorisez pour utiliser la mémorisation et que vous l'appelez ensuite 10 fois, Valeur sera 1.

Vous pouvez commencer à chercher comment mémoriser un état, de manière à pouvoir simuler une fonction qui mémorise un type de référence. Mais ce que vous mémorisez vraiment est l'ensemble des valeurs sur lesquelles la fonction fonctionne. Vous pouvez également pirater une fonction mémoisée ayant des effets secondaires de sorte que ses effets secondaires se produisent avant la mémorisation. Mais tout cela ne demande que des ennuis.

Si vous souhaitez implémenter la mémorisation dans une fonction prenant un type de référence, la bonne approche consiste à refactoriser la partie de la fonction qui ne fonctionne que sur les types de valeur et à la mémoriser, 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 mise en œuvre de la mémorisation que vous prenez a) fait la même chose, par des moyens plus obscurs, ou b) ne fonctionnera pas.

Answer 2

Eh bien, toute fonction, en théorie, est candidate à la mémorisation. Cependant, rappelez-vous que la mémoisation concerne avant tout le commerce d'espace pour la vitesse -

En général, cela signifie que plus l’état requis par une fonction ou dépendant de celle-ci pour calculer une réponse est important, plus le coût en espace est élevé, ce qui réduit l’opportunité de mémoriser la méthode.

Vos deux exemples sont essentiellement des cas dans lesquels il faudrait enregistrer davantage d’États. Cela a deux effets secondaires.

Tout d’abord, cela nécessitera beaucoup plus d’espace mémoire pour pouvoir mémoriser la fonction, car davantage d’informations devront être sauvegardées.

Deuxièmement, cela pourrait potentiellement ralentir la fonction mémo, car plus l’espace est grand, plus le coût de la recherche de la réponse est coûteux, ainsi que le coût de la recherche du résultat précédemment sauvegardé ou non.

En général, j’ai tendance à ne prendre en compte que les fonctions qui ont peu d’entrées possibles et peu d’espace de stockage, à moins que le calcul du résultat ne coûte très cher.

Je reconnais que ceci est vague, mais cela fait partie du "artistry" en architecture. Il n'y a pas de " droit " répondre sans implémenter les deux options (fonctions mémo et non mémo), profilage et mesure.

Answer 3

Vous avez déjà pensé à un moyen de fournir une solution AOP pour mémoriser la fonction Foo , que reste-t-il donc à résoudre?

Oui, vous pouvez passer un objet de complexité arbitraire en tant que paramètre à une fonction mémoisée, tant qu’il est immuable, comme le sont 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 convaincu que vous pouvez examiner le code de manière statique afin de conseiller les utilisateurs sur la question "Est-ce une bonne idée d'appliquer la mémorisation à la fonction Foo ?" / p>

Si vous en faites l’une de vos exigences, vous vous joindrez à un effort de recherche mondial qui dure depuis de nombreuses années. Cela dépend de votre ambition, je suppose.