Python - qualcuno ha un decoratore memoizing in grado di gestire argomenti non selezionabili?

Question

Sto usando il seguente decoratore di memoizing (dal grande libro Python Algorithms: Mastering Algorithms di base nel linguaggio Python ... lo adoro, btw).

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

Il problema con questo decoratore è che la cache basata sul dizionario significa che tutti i miei argomenti devono essere lavabili.

Qualcuno ha un'implementazione (o un tweak su questo) che consente argomenti inaffidabili (ad es. Dizionari)?

So che la mancanza di un valore di hash significa che la domanda "è presente nella cache?" diventa non banale, ma ho pensato di chiedere.

=== A cura di fornire un contesto ===

Sto lavorando ad una funzione che restituisce uno stile di Parnas "utilizza gerarchia" dato un dizionario di modulo: dipendenze. Ecco il programma di installazione:

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 

In modo che:

>>> 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 è la funzione che voglio Memoize per rendere questa configurazione più scalabile. Come implementato senza memoization, calcola il livello di dipendenze più volte (ad esempio 'a' è calcolato 8 volte penso nell'esempio sopra).

Grazie,

Mike

Answer 1

Ecco l'esempio di Alex Martelli Python Cookbook che mostrano come creare un decoratore Memoize usando cPickle per la funzione che prendono argomento mutabile (versione originale):

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] 

Ecco un link.

EDIT: Utilizzando il codice che avete dato e questo Memoize decoratore:

_level = MemoizeMutable(_level) 

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

print uses_hierarchy(equirements) 

sono riuscito a riprodurre questo:

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

Answer 2

Tecnicamente è possibile risolvere il problema disattivando la dict (o list o set) in una tupla. Per esempio:

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

cache[key] = func(..) 

Ma non vorrei farlo in memo, preferisco cambiare le funzioni che si desidera utilizzare memo su - per esempio, invece di accettare un dict dovrebbero solo accettare (key, value) coppie, invece di prendere liste o set dovrebbero solo prendere *args.

Answer 3

Non pesantemente testato, ma sembra funzionare:

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 

Answer 4

Poiché nessun altro lo ha menzionato, il P ython Wiki ha una libreria Decorator che include un numero di memoizing decorator patterns.

La mia preferenza personale è l'ultima, che consente al codice chiamante di trattare semplicemente il metodo come una proprietà pigramente valutata, piuttosto che un metodo. Ma mi piace l'implementazione here migliore.

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 

Nello stesso file linkato sopra c'è anche un decoratore lazy_dict, che consente di trattare una funzione come un dizionario con i valori pigramente-valutati.