중첩 함수가 중첩되지 않은 버전보다 훨씬 느린 이유는 무엇입니까?

Question

필자는 함수를 피클하려고 할 때 fibonacci 안에 메모 dict를 포함하려고합니다. 그러나 내 테스트에서 중첩 된 함수는 상당히 느린 것처럼 보이지만 필자가 memoized 함수를 사용할 때만 다른 버전의 fibonacci에서는이를 볼 수 없습니다.

내 모든 테스트 : 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 

Answer 1

당신은 부당한 이득을 중첩하지 않고 버전을 제공 실행 사이의 memo 사전을 청소하지 마십시오. 처음으로 timeit을 실행하면 fib이 실행되고 memo dict를 채운 다음 후속 실행에서 다시 사용합니다.

중첩 된 함수는 매번 새 memo 빈을 설정합니다.