Mémoisation de fonctions récursives en Python, mais uniquement pendant la durée de l'appel de niveau supérieur

Question

J'écris un analyseur descendant qui consiste en une fonction de niveau supérieur qui lance une analyse récursive du texte avec des fonctions de niveau inférieur . Notez que les fonctions de niveau inférieur n'appellent jamais la fonction de niveau supérieur, mais les fonctions de niveau inférieur sont mutuellement récursives. J'ai remarqué que l'analyseur s'exécute un peu lentement, et je soupçonne que cela est dû à une croissance exponentielle de la récursivité, car l'analyseur peut essayer à plusieurs reprises d'analyser le même type d'objet sur le même texte au même décalage, résultant dans l'effort gaspillé.

Pour cette raison, je souhaite mémoriser les appels de fonction de niveau inférieur, mais après le retour de la fonction de niveau supérieur, je souhaite effacer le cache de mémoisation pour libérer la mémoire. Cela signifie que si l'utilisateur appelle plusieurs fois la fonction de niveau supérieur avec les mêmes paramètres, le programme doit à nouveau parcourir toute la procédure d'analyse. Ma motivation est qu'il est peu probable que le même texte soit analysé plusieurs fois au niveau supérieur, de sorte que le surcoût de la mémoire n'en vaut pas la peine (chaque analyse générera un cache assez important).

Une solution possible consiste à réécrire toutes les fonctions de niveau inférieur à un argument de cache supplémentaire comme ceci:

def low_level_parse(text, start, cache): 
    if (text, start) not in cache: 
     # Do something to compute a result 
     # ... 
     cache[(text, start)] = result 

    return cache[(text, start)] 

et réécrire tous les appels vers les fonctions de bas niveau pour transmettre l'argument du cache (qui est initialement défini sur {} dans la fonction de niveau supérieur).

Malheureusement, il existe de nombreuses fonctions d'analyse de bas niveau, et chacune peut également appeler plusieurs fois d'autres fonctions d'analyse de bas niveau. Refactoriser le code pour implémenter la mise en cache de cette façon serait très fastidieux et sujet aux erreurs. Une autre solution serait d'utiliser des décorateurs, et je crois que ce serait mieux en termes de maintenabilité, mais je ne sais pas comment implémenter le décorateur memoize de telle sorte que son cache existe seulement au niveau supérieur. portée de la fonction.

J'ai également pensé à définir le cache comme une variable globale dans mon module, et l'effacer explicitement après le retour de la fonction de niveau supérieur. Cela m'épargnerait le besoin de modifier les fonctions de bas niveau pour prendre l'argument de cache explicitement, et je pourrais alors utiliser un décorateur memoize qui utilise le cache global. Mais je ne suis pas sûr que le cache global serait une bonne idée si cela est utilisé dans un environnement multithread.

Answer 1

Je trouve ce lien Decorators with Arguments que je pense est ce qui est nécessaire ici:

class LowLevelProxy: 

    def __init__(self, cache): 
     self.cache = cache 

    def __call__(self, f): 
     def wrapped_f(*args, **kwargs): 
      key = (f,args) # <== had to remove kwargs as dicts cannot be keys 
      if key not in self.cache: 
       result = f(*args, **kwargs) 
       self.cache[key] = result 

      return self.cache[key] 
     return wrapped_f 

NB chaque fonction qui est emballé aura sa propre section dans le cache.

vous pourriez être en mesure d'envelopper chacun de vos fonctions de bas niveau comme celui-ci:

@LowLevelProxy(cache) 
def low_level(param_1, param_2): 
    # do stuff