6

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 デコレータによって、関数内の各レベルの再帰が 3 レベルの再帰になっているように見えます。

functools.lru_cache関数をメモ化するために使用すると、再帰のレベルが 3 倍になるのはなぜですか?

4

1 に答える 1

5

デコレータは追加機能であるため、スタック内の1つのレベルを「使用」します。例：

>>> 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
于 2013-03-06T04:45:55.613 に答える