Memoize декораторы не запоминают (когда не используется синтаксис декоратора) - PullRequest
Новая
       4

Memoize декораторы не запоминают (когда не используется синтаксис декоратора)

1 голос
/ 22 марта 2012

У меня есть простой декоратор памятки: 

def funcmemo(f):
    memo = {}
    @wraps(f)
    def wrapper(*args):
    if args in memo:
        return memo[args]
    else:
        temp = f(*args)
        print "memoizing: ", args, temp  
        memo[args] = temp
        return temp
    return wrapper

Теперь, когда я использую его через токен "@", 

@funcmemo
def fib(n):
    print "fib called with:", n
    if n < 2: return n
    return fib(n-2) + fib(n-1)

res = fib(3)
print "result:", res

работает правильно, как видно на распечатке: 

fib called with: 3
fib called with: 1
memoizing:  (1,) 1
fib called with: 2
fib called with: 0
memoizing:  (0,) 0
memoizing:  (2,) 1
memoizing:  (3,) 2
result:  2

Однако, когда я делаю это: 

def fib(n):
    print "fib called with:", n
    if n < 2: return n
    return fib(n-2) + fib(n-1)

memfib = funcmemo(fib)
res = memfib(3)
print "result:", res

По-видимому, вызывается неокрашенный фиб, и только окончательное возвращаемое значение «достигает» кэша (очевидно, что приводит к огромному замедлению): 

fib called with: 3
fib called with: 1
fib called with: 2
fib called with: 0
fib called with: 1
memoizing:  (3,) 2
result: 2

Любопытно, что этот работает нормально: 

def fib(n):
    print "fib called with:", n
    if n < 2: return n
    return fib(n-2) + fib(n-1)

fib = funcmemo(fib)
res = fib(3)
print "result:", res

Кроме того, то же самое происходит с версией на основе классов: 

class Classmemo(object):
    def __init__ (self, f):
        self.f = f
        self.mem = {}
    def __call__ (self, *args):
        if args in self.mem:
            return self.mem[args]
        else:
            tmp = self.f(*args)
            print "memoizing: ", args, temp
            self.mem[args] = tmp
            return tmp

Проблема также возникает при использовании «анонимной» декорированной функции, например 

res = Classmemo(fib)(3)

Я был бы рад узнать о причинах этого.

Ответы [ 2 ]

5 голосов
/ 22 марта 2012

В этом нет ничего любопытного.Когда вы делаете 

memofib = funcmemo(fib)

Вы не изменяете функцию, на которую fib указывает каким-либо образом, но создаете новую функцию и указываете на нее имя memofib.

Таким образом, когда вызывается memofib, он вызывает функцию, на которую указывает имя fib - которая рекурсивно вызывает себя, а не memofib - так что никакого запоминания не происходит.

Вво втором примере вы делаете 

fib = funcmemo(fib)

, поэтому он вызывает себя рекурсивно, и запоминание происходит на всех уровнях.

Если вы не хотите перезаписывать имя fib в качестве декоратораверсия или ваш второй пример, вы можете изменить fib, чтобы получить имя функции: 

def fib(n, fibfunc):
    print "fib called with:", n
    if n < 2: return n
    return fibfunc(n-2, fibfunc) + fibfunc(n-1, fibfunc)

memofib = funcmemo(fib)
res = fib(3, memofib)

Вы также можете использовать комбинатор с фиксированной точкой , чтобы избежать передачи fibfunc каждый раз: 

def Y(f):
    def Yf(*args):
        return f(Yf)(*args)
    return f(Yf)

@Y
def fib(f):
    def inner_fib(n):
        print "fib called with:", n
        if n < 2: return n
        return f(n-2) + f(n-1)
    return inner_fib
2 голосов
/ 22 марта 2012

В случае, если ваш вопрос прост: , почему , я думаю, что ответ только потому, что вызов рекурсии с fib() вызывает функцию с именем fib(). Чтобы украсить это нужно заменить значение указателя fib; это не делается ни memfib = funcmemo(fib), ни версией класса.

...