1

バージョン 1 と 2 が同じ速度で実行される理由を誰か説明できますか? バージョン 2、3、および 4 にはほぼ同じ時間がかかると予想していました。

def fib(n):
    return n if n in [0, 1] else fib(n-2)+fib(n-1)

def memoize(fn):
    stored_results = {}

    def memoized(*args):
        try:
            return stored_results[args]
        except KeyError:
            #nothing cached
            result = stored_results[args] = fn(*args)
            return result

    return memoized

#version 1 (unmemoized)
print timeit.timeit('fib(35)', 'from __main__ import fib', number=1)
print fib, '\n'

#version 2
memo_fib = memoize(fib)
print timeit.timeit('memo_fib(35)', 'from __main__ import memo_fib', number=1)
print memo_fib, '\n'

#version 3 (wrapped)
fib = memoize(fib)
print timeit.timeit('fib(35)', 'from __main__ import fib', number=1)
print fib, '\n'

#version 4 (w/ decoration line)
@memoize
def fib(n):
    return n if n in [0, 1] else fib(n-2)+fib(n-1)

print timeit.timeit('fib(35)', 'from __main__ import fib', number=1)

結果：

version 1:  4.95815300941
<function fib at 0x102c2b320> 

version 2:  4.94982290268
<function memoized at 0x102c2b410> 

version 3:  0.000107049942017
<function memoized at 0x102c2b488> 

version 4:  0.000118970870972
4

2 に答える 2

5

あなたのmemoize関数は実際に に置き換えfibられてmemo_fibいるのではなく、新しい関数を返しているだけです。

その新しい関数は、メモ化されていない元の を再帰的に呼び出しますfib。

したがって、基本的には、最上位レベルのみをメモしています。

内fibでは、 への再帰呼び出しfibはモジュール グローバル名を使用しているだけです。(基本的に、関数は他の種類の値と変わらず、関数名も他の種類の名前と変わらないため、モジュール グローバル レベルで関数を定義すると、それが実行されます。たとえば、バイトコードを逆アセンブルすると、を使用すると、名前にdis.dis(fib)a が表示されます。)LOAD_GLOBALfib

したがって、簡単な修正は次のとおりです。

fib = memoize(fib)

またはmemoize、デコレータとして使用して、これを間違えにくくします。

つまり、例 3 と 4 です。

または、さらに簡単に、組み込みのlru_cacheデコレーターを使用します。(ドキュメントの 2 番目の例に注意してください。)

本当にこっそりしたい場合:fib関数本体内で定義します。fibグローバルではなく、定義するスコープからクロージャーセルとして参照することになります（逆アセンブリLOAD_DEREFではなく）。次に、そのスコープに到達してそのLOAD_GLOBALを置き換えることができます。つまり、再帰関数が「秘密裏に」メモ化され (実際のグローバルはメモ化されていませんが、再帰的に呼び出す関数はメモ化されています)、「安全に」(他の誰も参照を持っていません)それ自体を除いて閉鎖セルに）。 fibfibfib

于 2013-04-30T23:54:24.407 に答える
1

バージョン 2 では、メモ化されたバージョンを別の名前で保存したため、最初のバージョンと同じ回数だけ fib を呼び出すことになります。コール スタックは次のようになります。

memo_fib(35)
    fib(35)
        fib(34)
            fib(33)
        fib(33)

等

したがって、この場合、メモ化から実際には何の利益も得られません。

于 2013-04-30T23:56:23.097 に答える