Максимальная глубина рекурсии достигается быстрее при использовании functools.lru_cache

Я играл с мемоизацией и рекурсией в python 3.3.

Игнорируя тот факт, что Python — это не тот язык, на котором это нужно делать, я обнаружил, что получаю противоречивые результаты между использованием functools.lru_cache для запоминания и не использованием functools.lru_cache

Я не меняю предел рекурсии - он остается по умолчанию, который для меня равен 1000.

Чтобы проверить проблему, я написал простую рекурсивную функцию для суммирования чисел от 1 до i.

#!/usr/bin/python

def sumtil(i):
"""Recursive function to sum all numbers from 1 through i"""

    # Base case, the sum of all numbers from 1 through 1 is 1... 
    if i == 1:
        return 1
    else:
        return i+sumtil(i-1)

# This will not throw an exception
sumtil(998)

# This will throw an exception
sumtil(999)

Запустив эту функцию в обычном режиме, я могу с комфортом запустить sumtil(998), не достигая предела рекурсии. sumtil(999) или выше вызовет исключение.

Однако, если я попытаюсь украсить эту функцию @functools.lru_cache(), исключение ограничения рекурсии будет выдано 3 раза раньше при запуске sumtil(333)

#!/usr/bin/python

import functools 

@functools.lru_cache(maxsize=128)
def sumtil(i):
    """Recursive function to sum all numbers from 1 through i"""

    # Base case, the sum of all numbers from 1 through 1 is 1... 
    if i == 1:
        return 1
    else:
        return i+sumtil(i-1)

# This will not throw an exception
sumtil(332)

# This will throw an exception
sumtil(333)

Поскольку 332*3 = 996, а 333*3 = 999, мне кажется, что декоратор lru_cache заставляет каждый уровень рекурсии в моей функции стать тремя уровнями рекурсии.

Почему я получаю в три раза больше уровней рекурсии при использовании functools.lru_cache для запоминания функции?


python recursion memoization python-3.3
person Kiirani    schedule 06.03.2013    source источник

Ответы (1)


arrow_upward
5
arrow_downward

Поскольку декоратор — это дополнительная функция, он «использует» один уровень в стеке. Пример:

>>> def foo(f):
...   def bar(i):
...     if i == 1:
...       raise Exception()
...     return f(i)
...   return bar
...
>>> @foo
... def sumtil(i):
...     if i == 1:
...         return 1
...     else:
...         return i+sumtil(i-1)
...
>>> sumtil(3)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 5, in bar
  File "<stdin>", line 6, in sumtil
  File "<stdin>", line 5, in bar
  File "<stdin>", line 6, in sumtil
  File "<stdin>", line 4, in bar
Exception
>>>

Кроме того, если декоратор использует упаковку/распаковку аргументов, то используется дополнительный уровень (хотя я недостаточно осведомлен о среде выполнения Python, чтобы объяснить, почему это происходит).

def foo(f):
  def bar(*args,**kwargs):
    return f(*args,**kwargs)
  return bar

Максимум. глубина рекурсии превышена:

  • без украшений: 1000
  • без упаковки: 500
  • с упаковкой: 334
person mgibsonbr    schedule 06.03.2013