6

私は最近、デコレータを使用して再帰関数をメモ化する強力な方法について学びました。
「よしよし、遊んでみよう！」

class memoize:
    """Speeds up a recursive function"""
    def __init__(self, function):
        self.function = function
        self.memoized = {}

    def __call__(self, *args):
        try:
            return self.memoized[args]
        except KeyError:
            self.memoized[args] = self.function(*args)
            return self.memoized[args]
#fibmemo
@memoize
def fibm(n, current=0, next=1):
    if n == 0:
        return current
    else:
        return fibm(n - 1, next, current+next)

これtimeitは、実際にアルゴリズムを高速化すること を示しています。

fibmemo     0.000868436280412
fibnorm     0.0244713692225

「うわー、それは本当に役に立つかもしれません! 私はそれをどこまでプッシュできるのだろうか?」
140 を超える入力を使い始めると、すぐにRuntimeError: maximum recursion depth exceeded. 「ああ、クソ..」

少し検索した後、問題を解決するように見えるハックを見つけました。
「これもいいですね！遊んでみましょう」

class TailRecurseException:
    def __init__(self, args, kwargs):
        self.args = args
        self.kwargs = kwargs

def tail_call_optimized(g):
    """
    This function decorates a function with tail call optimization. It does this by throwing an exception
    if it is it's own grandparent, and catching such exceptions to fake the tail call optimization.

    This function fails if the decorated function recurses in a non-tail context.
    """
    def func(*args, **kwargs):
        f = sys._getframe()
        if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
            raise TailRecurseException(args, kwargs)
        else:
            while 1:
                try:
                    return g(*args, **kwargs)
                except TailRecurseException, e:
                    args = e.args
                    kwargs = e.kwargs
    func.__doc__ = g.__doc__
    return func

#fibtail
@tail_call_optimized
def fibt(n, current=0, next=1):
    if n == 0:
        return current
    else:
        return fibt(n - 1, next, current+next)

さて、メモ化を使用してフィボナッチ関数を高速化する方法があります。再帰の限界を押し上げる方法があります。両方を行う方法がわかりません。

#fibboth
@memoize
@tail_call_optimized
def fibb(n, current=0, next=1):
    if n == 0:
        return current
    else:
        return fibb(n - 1, next, current+next)

fibboth     0.00103717311766 
fibtail     0.274269805675
fibmemo     0.000844891605448
fibnorm     0.0242854266612

140未満の入力で機能するように見えるデコレータを組み合わせてみましたが、それを超える瞬間RuntimeError: maximum recursion depth exceededが発生します。それはほとんど@tail_call_optimized失敗のようなものです。 「なに…？」

質問：

  1. これらのデコレータを組み合わせる方法はありますか? もしそうなら、どのように？
  2. 組み合わせると、デコレータがより小さな入力に対して機能しているように見えるのはなぜですか?
4

4 に答える 4

4

ここには 2 つの問題があります。1 つ目は、@badcook が指摘するように、memoize デコレータが技術的に関数を非末尾再帰関数に変換することです。しかし、tail_call_optimized デコレーターはそれを気にしません。

2 つ目の問題と、それが機能しない理由は、fibb が呼び出されるたびに memoize デコレーターが追加のフレームをスタックに追加することです。そのため、自分の祖父母ではなく、自分の曾祖父母に似ています。チェックを修正することはできますが、memoize デコレータが効果的にバイパスされることに注意してください。

したがって、この話の士気は、テール コールの最適化とメモ化が混在しないことです。

もちろん、この特定の問題については、とにかく対数ステップ数で問題を解決する方法があります ( http://mitpress.mit.edu/sicp/full-text/book/book-ZHの SICP 演習 1.19 を参照してください)。 -11.html#%_sec_1.2.4詳細については)、この場合、問題はかなり意味がありません。しかし、それはこの質問の目的ではありません。

于 2013-11-01T22:48:47.453 に答える
1

ヒットしているのは、Python のスタック制限です。本当にこの道を進みたいのであれば、トランポリンと呼ばれるものを使い始める必要があります。これは基本的に、スタック スペースをヒープ スペースと交換します。

javascriptでこれらについて考える方法に関する良い記事と、より具体的なPythonの記事があります。その記事から、あなたが探しているのはこれです：

def trampoline(func):
  def decorated(*args):
    f = func(*args)
    while callable(f):
        f = f()
    return f
  return decorated

スタックを吹き飛ばすことなく物事を行うことができるように。それを読んでください。

編集：

また、これはトランポリンの単純な実装であることも付け加えておきます。これらのライブラリには、はるかに優れたバージョンがあるため、js の記事をリンクしました。その中で、末尾呼び出しの最適化のアイデアを保持しながら、多くの種類の依存計算を処理できる、より強力なバージョンを見ることができます。

于 2013-11-01T19:39:26.117 に答える