1

関数をピクルしようとしているときに、フィボナッチ内にメモ辞書を含めようとしています。ただし、私のテストでは、ネストされた関数はかなり遅いようですが、メモ化された関数を使用している場合にのみ、他のバージョンのフィボナッチではこれは見られません。

私のすべてのテスト: https://gist.github.com/dasickis/4733353

#!/usr/bin/env python

memo = {0: 0, 1: 1}

# Contract: [int > 0] -> [int > 0]
def fibonacci(n):
    """ Return the `x`th number in the fibonacci series. """
    if not n in memo:
        memo[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return memo[n]

#--------------------------#

# Contract: [int > 0] -> [int > 0]
def fibonacci_nested(n):
    memo = {0: 0, 1: 1}

    def fib(n):
        """ Return the `x`th number in the fibonacci series. """
        if not n in memo:
            memo[n] = fib(n - 1) + fib(n - 2)
        return memo[n]

    return fib(n)

#--------------------------#

import timeit
stmt = "assert fib(20) == 6765"

print "fibonacci"
print timeit.timeit(stmt, setup="from __main__ import fibonacci as fib")
print 

print "fibonacci_nested"
print timeit.timeit(stmt, setup="from __main__ import fibonacci_nested as fib")

出力:

fibonacci
0.263559103012

fibonacci_nested
11.4014730453
4

1 に答える 1

8

memo不当な利点をネストせずにバージョンを提供する実行間で辞書をクリーンアップしません。初めてtimeit実行すると辞書fibがいっぱいにmemoなり、その後の実行でそれが再利用されます。

ネストされた関数は、memo毎回新しい空のを設定します。

于 2013-02-07T19:20:55.520 に答える