Mise en cache des résultats d'une fonction avec deux paramètres en Python

Question

J'ai une méthode avec deux paramètres qui effectue des calculs complexes. Il est appelé très souvent avec les mêmes paramètres, donc j'utilise un dictionnaire pour la mise en cache. À l'heure actuelle cela ressemble quelque chose comme ceci:

def foo(self, a, b): 
    params = frozenset([a, b]) 
    if not params in self._cache: 
     self._cache[params] = self._calculate(a, b) 
    return self._cache[params] 

La raison de la construction du frozenset est que les paramètres peuvent être dans un ordre quelconque, mais le résultat sera le même. Je me demande s'il existe une solution plus simple (et surtout plus efficace) pour cela.

Answer 1

Votre code a deux problèmes:

(1) Il utilise la méthode ancienne dict.has_key() qui est lent et a disparu en Python 3.x. Au lieu de cela, utilisez "key in dict" ou "key not in dict".

Alors:

def foo(self, a, b): 
    params = frozenset([a, b]) 
    if params in self._cache: 
     self._cache[params] = self._calculate(a, b) 
    return self._cache[params] 

(2) "clé dict" est plus lisible, et expose le problème bien pire: votre code ne fonctionne pas! Si les arguments sont dans le dict, il recalcule. S'ils ne sont pas dans la dict, ils exploseront avec une KeyError. Pensez à copier/coller au lieu de taper à partir de la mémoire.

Alors:

def foo(self, a, b): 
    params = frozenset([a, b]) 
    if params not in self._cache: 
     self._cache[params] = self._calculate(a, b) 
    return self._cache[params] 

(3) Quelques autres suggestions d'efficacité:

def foo(self, a, b): 
    if a < b: 
     params = (a, b) 
    else: 
     params = (b, a) 
    try: 
     return self._cache[params] 
    except KeyError: 
     v = self._cache[params] = self._calculate(a, b) 
     return v 

Answer 2

Vous pouvez soit combiner les deux valeurs en une valeur de hachage comme str (a) + '\ 0' + str (b) et ensuite le mettre dans un cache, ou vous pouvez créer un tableau à deux dimensions pour que le cache [a] [b] renvoie la valeur que vous voulez.

Vous pouvez également transformer cette fonctionnalité en une fonction de type @decorator, puis vous pouvez réutiliser le décorateur sur plusieurs fonctions et conserver un emplacement de code pour la mise en cache.

Answer 3

Je voudrais juste le stocker dans le cache deux fois, une fois pour chaque commande.

def foo(self, a, b): 
    try: 
     return self._cache[(a, b)] 
    except KeyError: 
     value = self._calculate(a, b) 
     self._cache[(a, b)] = self._cache[(b, a)] = value 
     return value 

Answer 4

Vous pouvez utiliser beaker.cache pour cela (http://beaker.groovie.org/index.html)

# define a cache manager 
cache = CacheManager(dict_of_config_options) 

# in your class, apply a cache decorator 
@cache.cache('mycache') 
def foo(self, a,b): 
    return self._calculate 

Je pense que cela fonctionne comme vous le souhaitez par défaut. Je ne sais pas si cela fait partie de la clé. Il suppose que a, b sont pickleable.

Answer 5

Il n'y a rien de particulièrement inefficace ou compliqué sur la façon dont vous avez implémenté votre mise en cache; c'est essentiellement ce qui doit arriver. Cependant, ce n'est pas vraiment général.

Vous pouvez implémenter une sorte de stratégie de mise en cache plus généralisée, en utilisant des décorateurs si vous le souhaitez, par commodité. Une approche possible pourrait être:

class Memoizer(object): 
    def __init__(self): 
     self._cache = dict() 

    def memoize_unordered(self, f): 
     def wrapper(s, *args, **kwargs): 
      key = (s, f, frozenset(args), frozenset(kwargs.iteritems())) 
      if key not in self._cache: 
       print 'calculating', args, kwargs 
       self._cache[key] = f(s, *args, **kwargs) 
      return self._cache[key] 
     return wrapper 

    def memoize_ordered(self, f): 
     def wrapper(s, *args, **kwargs): 
      key = (s, f, tuple(args), frozenset(kwargs.iteritems())) 
      if key not in self._cache: 
       print 'calculating', args, kwargs 
       self._cache[key] = f(s, *args, **kwargs) 
      return self._cache[key] 
     return wrapper 

memoizer = Memoizer() 

class Foo(object): 

    @memoizer.memoize_unordered 
    def foo(self, a, b): 
     return self._calculate(a, b) 

    def _calculate(self, a, b): 
     return frozenset([a,b]) 

foo = Foo() 


results = [foo.foo(*a) for a in [(1, 5), (1, 5), (5, 1), (9, 12), (12, 9)]] 
for result in results: 
    print 'RESULT', result 

impression:

calculating (1, 5) {} 
calculating (9, 12) {} 
RESULT frozenset([1, 5]) 
RESULT frozenset([1, 5]) 
RESULT frozenset([1, 5]) 
RESULT frozenset([9, 12]) 
RESULT frozenset([9, 12]) 

L'inconvénient bien sûr, de mettre en œuvre la mise en cache hors de votre objet, est que les données du cache ne soit pas effacé lorsque votre objet disparaît , sauf si vous prenez quelques précautions pour que cela se produise.