2011-01-12 5 views
21

He estado usando el siguiente decorador de memoria (del gran libro Algoritmos de Python: Dominio de Algoritmos Básicos en el Lenguaje Python ... me encanta, por cierto).Python: ¿alguien tiene un decorador de memorando que pueda manejar argumentos irresolubles?

def memo(func): 
    cache = {} 
    @ wraps(func) 
    def wrap(*args): 
     if args not in cache: 
      cache[args] = func(*args) 
     return cache[args] 
    return wrap 

El problema con esto es que el decorador de diccionario basado en caché significa que todos mis argumentos deben ser hashable.

¿Alguien tiene una implementación (o una modificación de esta) que permite argumentos irresolubles (por ejemplo, diccionarios)?

Sé que la falta de un valor hash significa que la pregunta "¿está esto en el caché?" se vuelve no trivial, pero solo pensé en preguntar.

=== editado para dar un contexto ===

estoy trabajando en una función que devuelve un estilo de Parnas "utiliza la jerarquía" dado un diccionario de módulo: dependencias. Aquí está la configuración:

def uses_hierarchy(requirements): 
    """ 
    uses_hierarchy(requirements) 

    Arguments: 
    requirements - a dictionary of the form {mod: list of dependencies, } 

    Return value: 
    A dictionary of the form {level: list of mods, ...} 

    Assumptions: 
    - No cyclical requirements (e.g. if a requires b, b cannot require a). 
    - Any dependency not listed as a mod assumed to be level 0. 

    """ 

    levels = dict([(mod, _level(mod, requirements)) 
        for mod in requirements.iterkeys()]) 
    reversed = dict([(value, []) for value in levels.itervalues()]) 
    for k, v in levels.iteritems(): 
     reversed[v].append(k) 
    return reversed 


def _level(mod, requirements): 
    if not requirements.has_key(mod): 
     return 0 
    dependencies = requirements[mod] 
    if not dependencies: 
     return 0 
    else: 
     return max([_level(dependency, requirements) 
        for dependency in dependencies]) + 1 

Así que:

>>> requirements = {'a': [], 
...     'b': [], 
...     'c': ['a'], 
...     'd': ['a','b'], 
...     'e': ['c','d'], 
...     'f': ['e'] 
...     } 

>>> uses_hierarchy(requirements) 
{0: ['a', 'b'], 1: ['c', 'd'], 2: ['e'], 3: ['f']} 

_level es la función Quiero memoize para hacer esta configuración más escalable. Como se implementó sin memoria, calcula el nivel de dependencias varias veces (por ejemplo, 'a' se calcula 8 veces, creo que en el ejemplo anterior).

Gracias,

Mike

+1

Bueno, simplemente guárdelos en una lista como tuplas de '(args, result)', y repítalo. Como dices, sin embargo, no será rápido. –

+1

@Thomas K: Un caché que se vuelve más lento cuanto más elementos tiene, suena realmente contraproducente. –

+0

@ THC4k: Depende de lo que desee. Si va a alcanzar las mismas pocas posibilidades muchas veces, y la función es un gran cálculo o una solicitud de red lenta, podría ser más que suficiente. Y en una computadora moderna, puede ser bastante grande antes de que sea un problema. –

Respuesta

14

Aquí está el ejemplo de Alex Martelli Python Cookbook que muestran cómo crear un decorador memoize usando cPickle para la función que tienen argumento mutable (versión original):

import cPickle 

class MemoizeMutable: 
    def __init__(self, fn): 
     self.fn = fn 
     self.memo = {} 
    def __call__(self, *args, **kwds): 
     import cPickle 
     str = cPickle.dumps(args, 1)+cPickle.dumps(kwds, 1) 
     if not self.memo.has_key(str): 
      print "miss" # DEBUG INFO 
      self.memo[str] = self.fn(*args, **kwds) 
     else: 
      print "hit" # DEBUG INFO 

     return self.memo[str] 

Aquí es una link.

EDIT: Usando el código que has dado y esta memoize decorador:

_level = MemoizeMutable(_level) 

equirements = {'a': [], 
       'b': [], 
       'c': ['a'], 
       'd': ['a','b'], 
       'e': ['c','d'], 
       'f': ['e'] 
       } 

print uses_hierarchy(equirements) 

yo era capaz de reproducir este:

miss 
miss 
hit 
miss 
miss 
hit 
miss 
hit 
hit 
hit 
miss 
hit 
{0: ['a', 'b'], 1: ['c', 'd'], 2: ['e'], 3: ['f']} 
+0

@MikeRand: acabo de editar mi respuesta con su ejemplo, espero que pueda ayudar – mouad

+3

+1: El decapado es una forma interesante de trocear objetos mutables. Supongo que esto ganaría al iterar una lista para muchas posibilidades (debido al tiempo de búsqueda), pero la solución más simple tiene menos sobrecarga para algunos casos posibles. –

+0

Parece que funciona, muchas gracias. Solo para mi comprensión: ¿está cPickle serializando eficazmente los argumentos para hacer que la serialización sea la clave hashable? – MikeRand

6

Técnicamente se puede resolver este problema girando el dict (o list o set) en una tupla. Por ejemplo:

key = tuple(the_dict.iteritems()) 
key = tuple(the_list) 
key = tuple(sorted(the_set)) 

cache[key] = func(..) 

Pero yo no haría esto en memo, prefiero cambiar las funciones que desee utilizar en la nota - por ejemplo, en lugar de aceptar un dict que sólo debe aceptar (key, value) pares, en vez de tomar listas o conjuntos, simplemente deben tomar *args.

+5

Tendría que ordenar los pares clave/valor del diccionario también. – Ben

1

No probado en gran medida, pero parece que funciona:

from functools import wraps 

def memo(func): 
    cache = [] 
    argslist = [] 
    @ wraps(func) 
    def wrap(*args): 
     try: 
      result = cache[argslist.index(args)] 
      print 'cache hit' 
      return result 
     except ValueError: 
      argslist.append(args) 
      cache.append(func(*args)) 
      print 'cache miss' 
      return cache[-1] 
    return wrap 

d1 = { 'a':3, 'b':42 } 
d2 = { 'c':7, 'd':19 } 
d3 = { 'e':34, 'f':67 } 

@memo 
def func(d): 
    return sum(d.values()) 

print func(d1) 
# cache miss 
# 45 
print func(d2) 
# cache miss 
# 26 
print func(d3) 
# cache miss 
# 101 
print func(d2) 
# cache hit 
# 26 
+0

Devuelve una respuesta diferente a la que esperaba. Cuando se ejecuta en el ejemplo anterior, el resultado es {0: ['a', 'b'], 1: ['c'], 2: ['e', 'd', 'f']}. No estoy seguro de por qué 'd' se mueve del nivel 1 al nivel 2. – MikeRand

+0

@MikeRand: No lo sé, pensé que podría ser porque los argumentos almacenados eran mutables, así que intenté hacer copias profundas de ellos, pero eso no tuvo ningún efecto. Lo analizaré más y le informaré y/o modificaré mi respuesta. – martineau

2

Dado que nadie más lo ha mencionado, el P ython Wiki tiene una biblioteca decoradora que incluye un número de memoizing decorator patterns.

Mi preferencia personal es la última, que permite que el código de llamada simplemente trate el método como una propiedad evaluada de forma diferida, en lugar de un método. Pero me gusta la implementación here mejor.

class lazy_property(object): 
    '''Decorator: Enables the value of a property to be lazy-loaded. 
    From Mercurial's util.propertycache 

    Apply this decorator to a no-argument method of a class and you 
    will be able to access the result as a lazy-loaded class property. 
    The method becomes inaccessible, and the property isn't loaded 
    until the first time it's called. Repeated calls to the property 
    don't re-run the function. 

    This takes advantage of the override behavior of Descriptors - 
    __get__ is only called if an attribute with the same name does 
    not exist. By not setting __set__ this is a non-data descriptor, 
    and "If an instance's dictionary has an entry with the same name 
    as a non-data descriptor, the dictionary entry takes precedence." 
    - http://users.rcn.com/python/download/Descriptor.htm 

    To trigger a re-computation, 'del' the property - the value, not 
    this class, will be deleted, and the value will be restored upon 
    the next attempt to access the property. 
    ''' 
    def __init__(self,func): 
     self.func = func 
     self.name = func.__name__ 
    def __get__(self, obj, type=None): 
     result = self.func(obj) 
     setattr(obj, self.name, result) 
     return result 

En el mismo archivo vinculado anteriormente también hay un decorador lazy_dict, que permite tratar una función como un diccionario con valores evaluados con pereza.

Cuestiones relacionadas