[haskell] 이 피보나치 함수는 어떻게 메모됩니까?

이 피보나치 함수는 어떤 메커니즘으로 기억됩니까?

fib = (map fib' [0..] !!)                 
     where fib' 1 = 1                                                        
           fib' 2 = 1                                                        
           fib' n = fib (n-2) + fib (n-1)

관련 메모에서이 버전이 아닌 이유는 무엇입니까?

fib n = (map fib' [0..] !! n)                                               
     where fib' 1 = 1                                                        
           fib' 2 = 1                                                        
           fib' n = fib (n-2) + fib (n-1)

답변

하스켈 평가 메커니즘은 별로 필요가 값이 필요할 때, 그것을 계산하고 다시 요구되는 경우에 준비가 유지된다. 일부 목록을 정의 xs=[0..]하고 나중에 100 번째 요소 인을 요청 xs!!99하면 목록의 100 번째 슬롯이 “살아남” 99상태가되어 현재 번호를 보유하고 다음 액세스를 준비합니다.

이것이 바로 “목록을 통과하는”트릭이 악용하는 것입니다. 정상적인 이중 재귀 피보나치 정의 fib n = fib (n-1) + fib (n-2)에서 함수 자체가 맨 위에서 두 번 호출되어 지수 폭발을 일으 킵니다. 그러나 그 트릭으로 우리는 중간 결과에 대한 목록을 설정하고 “목록을 통해”진행합니다.

fib n = (xs!!(n-1)) + (xs!!(n-2)) where xs = 0:1:map fib [2..]

트릭은 해당 목록을 생성하고 해당 목록이를 호출하는 사이에 가비지 수집을 통해 사라지지 않도록하는 것 fib입니다. 이를 달성하는 가장 쉬운 방법 은 목록의 이름 을 지정 하는 것입니다. “네가 이름을 지으면 그대로 남아있을 것이다.”

첫 번째 버전은 단형 상수를 정의하고 두 번째 버전은 다형성 함수를 정의합니다. 다형성 함수는 제공해야 할 다른 유형에 대해 동일한 내부 목록을 사용할 수 없으므로 공유 , 즉 메모가 없습니다.

첫 번째 버전에서 컴파일러는 상수 하위 표현식 ( )을 제거하고이를 별도의 공유 가능한 엔티티로 만드는 등 관대map fib' [0..] 하지만 그렇게 할 의무는 없습니다. ^{실제로 우리 가 자동으로 수행하는 것을 원하지 않는 경우가 있습니다.}

( 편집 🙂 다음 재 작성을 고려하십시오.

fib1 = f                     fib2 n = f n                 fib3 n = f n          
 where                        where                        where                
  f i = xs !! i                f i = xs !! i                f i = xs !! i       
  xs = map fib' [0..]          xs = map fib' [0..]          xs = map fib' [0..] 
  fib' 1 = 1                   fib' 1 = 1                   fib' 1 = 1          
  fib' 2 = 1                   fib' 2 = 1                   fib' 2 = 1          
  fib' i=fib1(i-2)+fib1(i-1)   fib' i=fib2(i-2)+fib2(i-1)   fib' i=f(i-2)+f(i-1)

따라서 실제 이야기는 중첩 된 범위 정의에 관한 것 같습니다. 첫 번째 정의에는 외부 범위가 없으며 세 번째는 외부 범위를 호출하지 않고 fib3동일한 수준 을 호출하도록주의 합니다 f.

의 값에 따라 (이론상) 다르게 정의 될 수fib2 있기 때문에 각각의 새로운 호출은 중첩 된 정의를 새로 만드는 것 같습니다 ( 이를 지적한 Vitus와 Tikhon에게 감사드립니다). 첫 번째 (고화질)로 더 없다 에 의존하고, 세 번째에 의존하지만 각각 별도의 호출이 로 호출 이 특정 호출 내부와 동일한 수준의 범위에서만 호출 정의에주의 인 동일하므로, 도착 해당 호출에 재사용 (즉 공유)됩니다 .nnfib3ffib3xsfib3

그러나 컴파일러가 위의 모든 버전의 내부 정의가 실제로 외부 바인딩과 독립적 이라는 것을 인식하는 것을 배제하지 않고 n결국 람다 리프팅 을 수행하여 전체 메모 화 (다형성 정의 제외)를 수행합니다. 사실 이것은 단형 유형으로 선언되고 -O2 플래그로 컴파일 될 때 세 가지 버전 모두에서 정확히 발생합니다. 다형성 유형 선언을 사용하면 fib3로컬 공유를 표시하고 fib2공유하지 않습니다.

궁극적으로 컴파일러 및 사용 된 컴파일러 최적화, 테스트 방법 (GHCI에서 파일로드, 컴파일 여부, -O2 사용 여부, 독립 실행 형), 모노 모픽 또는 다형성 유형을 가져 오는지 여부에 따라 동작이 수행 될 수 있습니다. 완전히 변경-로컬 (호출 당) 공유 (즉, 각 호출에 대한 선형 시간), 메모 (즉, 첫 번째 호출에 선형 시간, 후속 호출에 동일하거나 더 작은 인수가있는 후속 호출에 0 시간)를 표시하는지 또는 전혀 공유하지 않는지 ( 지수 시간).

짧은 대답은 컴파일러라는 것입니다. 🙂

답변

나는 완전히 확신하지 못하지만 여기에 교육받은 추측이 있습니다.

컴파일러는 이것이 fib n다를 수 있다고 가정 n하므로 매번 목록을 다시 계산해야합니다. where명령문 내부의 비트는 결국에 의존 할 수n 있습니다. 즉,이 경우 전체 숫자 목록은 본질적으로의 함수입니다 n.

없는 버전 n은 목록을 한 번 생성하고 함수로 래핑 할 수 있습니다. 이 목록 은n 전달 된 값에 의존 할 수 없으며 확인하기 쉽습니다. 목록은 색인화되는 상수입니다. 물론 이것은 느리게 평가되는 상수이므로 프로그램은 전체 (무한) 목록을 즉시 가져 오려고하지 않습니다. 상수이기 때문에 함수 호출에서 공유 할 수 있습니다.

재귀 호출은 목록에서 값을 조회하기 만하면되기 때문에 전혀 기억되지 않습니다. fib버전은 한 번 느리게 목록을 생성 하므로 중복 계산을 수행하지 않고 답을 얻을 수있을만큼만 계산합니다. 여기서 “lazy”는 목록의 각 항목이 썽크 (평가되지 않은 표현식)임을 의미합니다. 당신이하면 않는 썽 크는를 평가, 그렇게 그에게 어떤 계산을 반복 않습니다 다음에 액세스 값이된다. 목록은 통화간에 공유 할 수 있으므로 이전 항목은 모두 다음 항목이 필요한 시간에 이미 계산됩니다.

본질적으로 GHC의 게으른 의미 체계를 기반으로 한 영리하고 임대료가 낮은 동적 프로그래밍 형식입니다. 나는 표준 이 엄격하지 않아야한다고 만 명시하고 있으므로 준수 컴파일러는 잠재적으로이 코드를 메모 하지 않기 위해 컴파일 할 수 있습니다 . 그러나 실제로 모든 합리적인 컴파일러는 게으르다.

두 번째 사례가 작동하는 이유에 대한 자세한 내용은 재귀 적으로 정의 된 목록 이해 (zipWith 측면에서 fibs)를 읽어보세요 .

답변

첫째,로 컴파일 된 ghc-7.4.2를 사용하면 -O2메모리가없는 버전이 그렇게 나쁘지 않습니다. 피보나치 수의 내부 목록은 함수에 대한 각 최상위 호출에 대해 여전히 메모됩니다. 그러나 다른 최상위 수준의 호출에 대해 메모 할 수 없으며 합리적으로 저장할 수도 없습니다. 그러나 다른 버전의 경우 목록이 통화간에 공유됩니다.

이는 단 형성 제한 때문입니다.

첫 번째는 단순 패턴 바인딩 (이름 만, 인수 없음)에 의해 바인딩되므로 단일형 제한에 따라 단일형 유형을 가져와야합니다. 추론 된 유형은 다음과 같습니다.

fib :: (Num n) => Int -> n

이러한 제약 조건은 기본 선언이 없으면으로 기본 설정 Integer되어 형식을 다음과 같이 수정합니다.

fib :: Int -> Integer

따라서 [Integer]메모 할 목록 (유형 )이 하나뿐입니다.

두 번째는 함수 인수로 정의되므로 다형성으로 유지되며 내부 목록이 호출간에 메모 된 경우 .NET의 각 유형에 대해 하나의 목록을 메모해야합니다 Num. 실용적이지 않습니다.

단 형성 제한을 비활성화하거나 동일한 유형 서명을 사용하여 두 버전을 모두 컴파일하고 둘 다 정확히 동일한 동작을 나타냅니다. (이전 컴파일러 버전에서는 사실이 아니 었습니다. 어떤 버전이 먼저 실행되었는지 모르겠습니다.)

답변

Haskell에는 메모 기능이 필요하지 않습니다. 경험적 프로그래밍 언어에만 해당 기능이 필요합니다. 그러나 Haskel은 기능적 언어이며 …

그래서 이것은 매우 빠른 피보나치 알고리즘의 예입니다.

fib = zipWith (+) (0:(1:fib)) (1:fib)

zipWith는 표준 Prelude의 기능입니다.

zipWith :: (a->b->c) -> [a]->[b]->[c]
zipWith op (n1:val1) (n2:val2) = (n1 + n2) : (zipWith op val1 val2)
zipWith _ _ _ = []

테스트:

print $ take 100 fib

산출:

[1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,2880067194370816120,4660046610375530309,7540113804746346429,12200160415121876738,19740274219868223167,31940434634990099905,51680708854858323072,83621143489848422977,135301852344706746049,218922995834555169026,354224848179261915075,573147844013817084101]

경과 시간 : 0.00018 초