하스켈에서 가장 효율적으로 메모를하는 방법은 무엇입니까?

Question

하스켈에서 재귀 함수를 메모하는 가장 빠른 방법은 무엇입니까?

배경 : 최근 저는 하스켈에서 프로젝트 오일러 문제를 해결했습니다. 많은 사람들은 재귀 적으로 정의 된 조합 또는 숫자 이론적 함수, 예를 들어 피보나치 수의 많은 계산을 요구합니다. 성능이 현저히 향상되면 이러한 기능을 메모하면 즉, 나중에 사용하기 위해 결과가 캐싱됩니다.

이 문제에 대한 많은 해결책을 보았습니다. 가장 우아한 것 같습니다 this. 하나는 Data.IntMap (또는 해시 테이블) 및 상태 모나드를 사용합니다. this answer에서 제안 된 트리 기반 솔루션은 매우 보편적 인 것처럼 보입니다. 다른 예를 들면 this blog post을 참조하십시오. 내장 함수를 사용하는 다른 솔루션을 보았습니다. 섹션 2에 fix이있는 here이 있으며 추가 작업없이 컴파일러가 massaged into memoizing 일 수 있습니다. 또한 prebuilt solutions 몇 개가 있습니다.

Project Euler에서 사용되는 종류의 함수에 대해 어떤 메모 작성 방법이 가장 빠른지 궁금합니다. 내 직관은 해시 테이블이 명령형 언어에서 선호하는 사전 구조 인 것처럼 보이기 때문에 해시 테이블 라이브러리가 있다고 말합니다. 순수 기능 트리 솔루션은 시원하지만 내 인터넷 검색, 그들은 몇 가지 의견이 질문에 대답하기 너무 광범위하고, 동의 반사에 말했다 strictly worse than hash tables in terms of asymptotic performance.

편집

있어 나에게 말한다. 따라서 피보나치 수를 재귀 적으로 계산하는 함수와 카탈로니아의 숫자를 재귀 적으로 계산하는 함수의 두 가지 함수를 기억해 보겠습니다. 큰 n에 대해 여러 번이 함수를 계산하고 싶습니다.

나는 이것들에 대한 명확한 공식이 있음을 알고 있지만 무시해 보도록하겠습니다. 여기서 중요한 점은 memoization 기술을 벤치마킹하기 위해 그것을 사용하는 것이기 때문입니다.

Answer 1

피보나치 번호를 찾으려고 할 때 기억해야하는 숫자는 이전의 두 숫자뿐입니다. 당신은 (f n-1, f n)과 같은 튜플로 그것을 할 수 있고 각 루프에이 튜플을 업데이트합니다. 튜플을 업데이트하는 것은 포인터 조작을 통해 이루어지며 계산 비용이 들지 않습니다.

는 깨끗하고 약간 똑똑한 대안은 다음과 같습니다

fibs :: [Integer] 
fibs = fibcreator 0 1 
    where 
    fibcreator a b = a : fibcreator b (a+b) 

nth = take n fibs 

하지만 내가 본 최고의 알고리즘 중 하나가 이것이다 :

1. 이의이 행렬 m = [E11 = 1을 정의 할 수 있습니다, E12 = 1, E21 = 1, E22 = 0]
2. 우리 m을 계산하는 n 번째 피보나치 수 도착 '= m^(N-1)
행렬의 m에
3. E11 소자 'n 번째 피보나치 수
012 인 3,516,

지금 여기에서 좋은 것은 17 피보나치 수를 얻기 위해 우리가

m' = ((((m^2)^2)^2)^2) * m 

이 크게 computaion 시간을 단축하고 수동적 알고리즘 내에서 메모이 제이션을 내장 할 수 있다는 것입니다. Punchline은 Haskell이 이미이 알고리즘을 사용하여 power 함수를 계산하므로 구현할 필요가 없다는 것입니다.전체 구현은 다음과 같습니다

data Matrix = Matrix Integer Integer Integer Integer 

instance Num Matrix where 
    (*) (Matrix a11 a12 a21 a22) (Matrix b11 b12 b21 b22) 
    = Matrix (a11*b11 + a12*b21) (a11*b12 + a12*b22) (a21*b11 + a22*b21) (a21*b12 + a22*b22) 

fib4 :: Integer -> Integer 
fib4 0 = 0 
fib4 n = x 
    where 
    (Matrix x _ _ _) = Matrix 1 1 1 0^(n-1)