Может ли декоратор украсить рекурсивную функцию? - PullRequest
Новая
       15

Может ли декоратор украсить рекурсивную функцию?

2 голосов
/ 05 февраля 2020

Я хотел увидеть разницу в стоимости времени между двумя способами вычисления последовательности Фибоначчи: Сначала я создал декоратор, добавив функцию «стоимость времени вывода» в функцию: 

def time_cost(func):
    def wed(n):
        start = time.time()
        func(n)
        stop = time.time()
        print(stop-start)
    return wed

Затем я написал первый функция: 

@time_cost
def DP_F(n):
    f = [1,1]
    while len(f)<n:
    f.append(f[len(f)-1]+f[len(f)-2])
    return f

Работает хорошо 

>>> DP_F(10)
0.0
>>> DP_F(100)
0.0
>>> DP_F(10000)
0.007944107055664062

Но когда я создаю вторую функцию с декоратором, что-то не так произошло: 

@time_cost
def R_F(n):
    if n<=2:
        return 1
    else:
        return R_F(n-1)+R_F(n-2)

Возникла ошибка, когда некоторые из может быть пропущен вывод 

>>> R_F(10)
0.0
0.0
Traceback (most recent call last):
  File "<pyshell#44>", line 1, in <module>
    R_F(10)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
TypeError: unsupported operand type(s) for +: 'NoneType' and 'NoneType'

То есть декоратор Python не может декорировать рекурсивную функцию?

1 Ответ

2 голосов
/ 05 февраля 2020

Непосредственная проблема заключается в том, что wed не возвращает возвращаемое значение func. Это легко исправить. 

def time_cost(func):
    def wed(n):
        start = time.time()
        <b>n = </b>func(n)
        stop = time.time()
        print(stop-start)
        <b>return n</b>
    return wed

Однако, теперь посмотрите, что происходит, когда вы звоните R_F(3). 

>>> R_F(3)
9.5367431640625e-07
1.1920928955078125e-06
0.0001671314239501953
2

Вы получаете 3 раз: по одному на рекурсив вызов. Это происходит потому, что исходная функция вызывает то, с чем связана R_F, которая теперь является функцией wed, а не фактической функцией Фибоначчи.

Нечто подобное лучше обрабатывать с помощью диспетчера контекста. 

from contextlib import contextmanager

@contextmanager
def time_cost():
    start = time.time()
    yield
    stop = time.time()
    print(stop - start)

with time_cost():
    R_F(3)

Отступление

В некотором смысле Python не имеет рекурсивных функций. Функция не может вызывать сама себя, а только некоторая функция, связанная с именем, которое вы ожидаете , будет ссылаться на вашу функцию. Назовите это «кооперативная рекурсия».

Например, рассмотрим стандартный пример рекурсивной функции, факториал. 

def fact(x):
     return 1 if x == 0 else x * fact(x-1)

Мы можем легко сломать это, связав имя fact. 

g = fact  # save a reference to the original function
def fact(x):
   print("Broken")
   return 0

Теперь g(3) печатает Broken и возвращает 0, потому что он попытается вызвать все, что fact связано с сейчас , а не то, с чем fact было связано прежде чем переопределить его.

Если вы хотите "безопасную" рекурсивную функцию, вам придется определить ее в терминах частного рекурсивного помощника. 

def fact(x):
    def helper(x):
        return 1 if x == 0 else x * helper(x - 1)
    return helper(x)

Теперь вы можете безопасно декорировать fact, потому что независимо от того, с чем связан fact (будь то оригинал или декорированная функция), helper никогда не восстанавливается.

...