이 피보나치 기능은 어떻게 기억됩니까?

이 피보나치 기능은 어떻게 기억됩니까?

---

이 피보나치 기능은 어떤 메커니즘으로 기억됩니까?

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)                    

---

Haskell의 평가 메커니즘은 필요합니다 . 값이 필요할 때 계산되고 다시 요청 될 경우를 대비하여 준비됩니다. 리스트를 정의 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)

실제 이야기는 중첩 된 범위 정의에 관한 것 같습니다. 첫 번째 정의에는 외부 스코프가 없으며 세 번째는 outer-scope를 호출하지 말고 fib3동일한 수준 을 호출하도록주의 하십시오 f.

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

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

궁극적으로, 컴파일러 및 사용 된 컴파일러 최적화 및 테스트 방법 (GHO에서 파일로드, 컴파일 여부에 관계없이 -O2를 사용하거나 사용하지 않거나 독립형) 및 동작이 단일형인지 다 형형인지 여부에 따라 다릅니다. 로컬 (통화 당) 공유 (즉, 각 통화의 선형 시간), 메모 (예 : 첫 번째 통화의 선형 시간 및 동일하거나 작은 인수를 가진 후속 통화의 0 시간)를 표시하는지 또는 전혀 공유하지 않는지 (완전히 변경) 지수 시간).

짧은 대답은 컴파일러입니다. :)

---

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

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

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

재귀 호출은 목록에서 값을 찾아야하기 때문에 전혀 메모되지 않았습니다. fib버전은 한 번만 지연 목록을 작성 하기 때문에 중복 계산을 수행하지 않고 답변을 얻을 수있을 정도로만 계산합니다. 여기서 "게으른"은 목록의 각 항목이 썽크 (평가되지 않은 식)임을 의미합니다. 당신이하면 않는 썽 크는를 평가, 그렇게 그에게 어떤 계산을 반복 않습니다 다음에 액세스 값이된다. 통화간에 목록을 공유 할 수 있으므로 이전 항목은 모두 다음에 필요한 시간에 따라 이미 계산됩니다.

It's essentially a clever and low-rent form of dynamic programming based on GHC's lazy semantics. I think the standard only specifies that it has to be non-strict, so a compliant compiler could potentially compile this code to not memoize. However, in practice, every reasonable compiler is going to be lazy.

For more information about why the second case works at all, read Understanding a recursively defined list (fibs in terms of zipWith).

---

First, with ghc-7.4.2, compiled with -O2, the non-memoised version isn't so bad, the internal list of Fibonacci numbers is still memoised for each top-level call to the function. But it is not, and cannot reasonably, be memoised across different top-level calls. However, for the other version, the list is shared across calls.

That is due to the monomorphism restriction.

The first is bound by a simple pattern binding (only the name, no arguments), therefore by the monomorphism restriction it must get a monomorphic type. The inferred type is

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

and such a constraint gets defaulted (in the absence of a default declaration saying otherwise) to Integer, fixing the type as

fib :: Int -> Integer

Thus there's just one list (of type [Integer]) to memoise.

The second is defined with a function argument, thus it remains polymorphic, and if the internal lists were memoised across calls, one list would have to be memoised for each type in Num. That isn't practical.

Compile both versions with the monomorphism restriction disabled, or with identical type signatures, and both exhibit exactly the same behaviour. (That wasn't true for older compiler versions, I don't know which version first did it.)

---

You don't need memoize function for Haskell. Only empirative programming language need that functions. However, Haskel is functional lang and...

So, this is example of very fast Fibonacci algorithm:

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

zipWith is function from standard Prelude:

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

Test:

print $ take 100 fib

Output:

[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]

Time elapsed: 0.00018s

참고URL : https://stackoverflow.com/questions/11466284/how-is-this-fibonacci-function-memoized