파이썬 - 함수에서 사전 수정

Question

좋아,이 질문은 조금 이상하지만, 나는 이것을 이렇게 할 수 있을지 궁금해하고 있었다.

저는 프로그래밍에 관심이 많기 때문에 간단한 피보나치 넘버 생성기를 사용하고 있습니다.

def f(n): 
    if n == 1: return 1 
    if n == 2: return 2 
    else: 
     return f(n-1) + f(n-2) 

을하고 내 컴퓨터에 f(30)을 15 초를 복용, 매우 느리게 실행 : 그래서 나는 이것을 썼다.

{'f(1)':1,'f(2)':2,'f(3)':3,'f(4)':5} 등 : 기본적과 같이 사전에 이전 결과를 저장

def f(n): 
    global a 
    if n == 1: return 1 
    if n == 2: return 1 
    else: 
     if "fib(%s)" % n in a: 
      return a["fib(%s)" % n] 
     else: 
      z = f(n-1) + f(n-2) 
      a["fib(%s)" % n] = z 
      return z 

: 그래서 나는이를 썼다. 함수에서 그 결과가 해당 사전에 있는지 확인한 다음 모든 계산을 다시해야하는 대신 해당 결과를 사용합니다.

이렇게 빨라졌습니다. 나는 f(100)을 할 수 있고 즉시 나타납니다. 500의 간격으로 가면서, 나는 f(4000)에 도착했다. 그리고 그것은 아직도 순간이었다. 한 가지 문제는 사전이 어리석게 커지고 있다는 것입니다.

그래서 함수의 끝에 a = {}을 추가했는데 작동하지 않았습니다. 그것은 여전히 ​​방대한 표제어로 a을 남겼습니다.

그래서이 일을 :

이

def f(n): 
    global a 
    if n == 1: return 1 
    if n == 2: return 1 
    else: 
     if "fib(%s)" % n in a: 
      return a["fib(%s)" % n] 
     else: 
      z = f(n-1) + f(n-2) 
      a["fib(%s)" % n] = z 
      return z 
    a = {} 

작동하지 않았다. 나는이 작업을 수행하는 경우 만 :

def f(n): 
    global a 
    if n == 1: return 1 
    if n == 2: return 1 
    else: 
     if "fib(%s)" % n in a: 
      return a["fib(%s)" % n] 
     else: 
      z = f(n-1) + f(n-2) 
      a["fib(%s)" % n] = z 
      return z 
# now run the function 
f(100) 
a = {} 

a는 빈 사전에 리셋됩니다. 왜 이런 일이 일어나고 어떻게 해결할 수 있습니까?

Answer 1

a = {} 함수 내의 명령문이 실행되지 않았습니다. 그 전에 실행 가능한 모든 경로는 return에 도달합니다. WAS가 실행되면 결과를 좋아하지 않을 것입니다. 함수에 대한 모든 단일 재귀 호출에서 실행되었으므로 사전에 두 개 이상의 항목을 포함하지 않습니다! 당신은 어쨌든 가장 바깥 쪽 호출을 탐지하고 그곳에있는 dict 만 지우거나 두 번째 예제 에서처럼 재귀 외부에서 지우기 만하면됩니다.

사전의 크기는 긴 문자열 키를 사용하는 이상한 결정에서 비롯된 것입니다. 숫자 자체 (a[n] = z에서와 같이)로 키잉하면 훨씬 더 컴팩트하게됩니다.

가 : 귀하의 질문에도 불구하고

Answer 2

(나중에 참조하십시오.이 기술은 "메모이 제이션"로 알려져, 이전 함수 호출의 결과를 저장하는 여기로 왔어요), 당신이 정말로 원하는 것은 인 피보나치 수식을 계산하는 더 빠른 방법 이죠? 원래 방식의 문제점은 매우 우아하고 코드 작성이 쉽지만 재발은 매우 느립니다. 피보나치 서열은 가까운 형태의 해법을 가지고 있습니다. 코드 속도를 높이려면이 수학을 직접 수행해야합니다. F (0) = 0, F (1) = 1, F (k) = F (k-1) + F (k-2) k = 2로 피보나치 시퀀스 F (i) 3, ...이 시퀀스에 대한 해답은 다음과 같다. (여기서는 설명하지 않겠다.) F (k) = (1/sqrt (5)) * (a^k - b^k) 여기서 a = (1 + sqrt (5))/2 및 b = (1 - sqrt (5))/2이다. 는 따라서, 당신의 코드는 다음과 같이 구현 될 수있다 :

def f(n): 

    a = (1 + 5**.5)/2 
    b = (1 - 5**.5)/2 
    F = (a**n - b**n)/5**.5 
    F = int(round(F)) #necessary to get an integer without the decimal part of the approximation. Afterall, you are working with irrational numbers. 
    return F 

이 코드 스케일 아주 잘위한 N의 큰 값.