Monad.Memo와 Memoization with Haskell의 상호 회귀

Question

상호 재귀 구현을 사용하여 Haskell에서 몇 가지 동적 프로그래밍을하고 있습니다.

나는 메모 작성을 사용하여 작업 속도를 높이기로 결정했습니다.

Monad.Memo는 MemoT 변압기를 제공합니다. 그러나 Map은 저장된 값을 내부 표현으로 사용합니다. 그리고 이것은 나에게 크기의 속도 향상을 주었지만 여전히 충분하지는 않습니다.

lib는 내부 저장소로 배열 기반 및 벡터 기반 구현을 지원하지만 단순한 재귀를 위해서만 작동하며 MemoT와 같은 상호 변 경을 위해 변압기를 찾지 못했습니다.

효과적인 벡터 기반 내부 표현 (있는 경우)을 사용하여 상호 재귀 메모를 수행하는 가장 좋은 방법은 무엇입니까?

내 다음 질문은 메모 효과에 관한 것입니다. 따라서 첫 번째 실행 중에는 더 많은 시간을, 연속 실행에서는 훨씬 적은 시간이 걸릴 것으로 예상했습니다. 하지만 ghci에서 실행될 때마다 매번 걸리는 시간은 같습니다. 첫 번째와 두 번째 차이점이 없습니다. 나는 다음과 같이 시간을 측정했다 :

timeit $ print $ dynamic (5,5) 

역동적 인 내 기능. 다음과 같이

전체 구현은 다음과 같습니다

import Control.Monad.Memo 
import Control.Monad.Identity 

type Pos = (Int, Int) 

type MemoQ = MemoT (Int, Int, Int) [Int] 
type MemoV = MemoT (Int, Int, Int) Int 
type MemoQV = MemoQ (MemoV Identity) 

-- we are moving to (0,0) as we can always shift the world by substituting variables 
-- due to symmetry of cost function it is enougth to solve for only positive x and y 
dynamic :: Pos -> [Int] 
dynamic (x, y) = lastUnique $ map (evalQ x y) [1 ..] 
    where lastUnique (x0:x1:xs) | x0 == x1 = x0 
           | otherwise = lastUnique (x1:xs) 

evalQ :: Int -> Int -> Int -> [Int] 
evalQ x y n = startEvalMemo . startEvalMemoT $ fqmon x y n 

fqmon :: Int -> Int -> Int -> MemoQV [Int] 
fqmon _ _ 0 = return [0,0,0,0] 
fqmon x y n = do 
    let pts = neighbours (x, y) 
    let v = for3 memol1 fvmon n 
    let c = cost (x, y) 
    let q = fmap (c +) . uncurry v 
    traverse q pts 

fvmon :: Int -> Int -> Int -> MemoQV Int 
fvmon _ 0 0 = return 0 
fvmon 0 x y = return $ cost (x, y) 
fvmon n x y | limit  = return 1000000 
      | otherwise = liftM minimum $ for3 memol0 fqmon x' y' (n - 1) 
      where x' = abs x 
       y' = abs y 
       limit = x' > 25 || y' > 25 

cost :: Pos -> Int 
cost (x, y) = abs x + abs y 

neighbours :: Pos -> [Pos] 
neighbours (x, y) = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)] 

---

추가 :

#liqui의 의견에 따르면 내가 memcombinators을 시도했다.

type Pos = (Int, Int) 

dynamic :: Int -> Int -> [Int] 
dynamic x y = lastUnique $ map (fq x y) [1 ..] 
    where lastUnique (x0:x1:xs) | x0 == x1 = x0 
           | otherwise = lastUnique (x1:xs) 

fq :: Int -> Int -> Int -> [Int] 
fq _ _ 0 = [0, 0, 0, 0]   -- Q at 0 step is 0 in all directions 
fq x y n = (cost (x, y) +) . (uncurry $ fv n) <$> neighbours (x, y) 

fv :: Int -> Int -> Int -> Int 
fv _ 0 0 = 0    -- V at (0, 0) is 0 at any atep 
fv 0 x y = cost (x, y)  -- V at 0 step is a cost 
fv n x y = minimum $ fq x y (n - 1) 

cost :: Pos -> Int 
cost (x, y) = abs x + abs y 

neighbours :: Pos -> [Pos] 
neighbours (x, y) = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)] 

그런 다음 내 시도가 memization하는 (만 변경된 부분) :

dynamic :: Int -> Int -> [Int] 
dynamic x y = lastUnique $ map (fqmem x y) [1 ..] 
    where lastUnique (x0:x1:xs) | x0 == x1 = x0 
           | otherwise = lastUnique (x1:xs) 
-- memoizing version of fq 
fqmem :: Int -> Int -> Int -> [Int] 
fqmem x y n = fqmem' x y n 
    where fqmem' = memo3 integral integral integral fq 

-- memoizing version of fv 
fvmem :: Int -> Int -> Int -> Int 
fvmem n x y = fvmem' n x y 
    where fvmem' = memo3 integral integral integral fv 

fq :: Int -> Int -> Int -> [Int] 
fq _ _ 0 = [0, 0, 0, 0]   -- Q at 0 step is 0 in all directions 
fq x y n = (cost (x, y) +) . (uncurry $ fvmem n) <$> neighbours (x, y) 

fv :: Int -> Int -> Int -> Int 
fv _ 0 0 = 0    -- V at (0, 0) is 0 at any atep 
fv 0 x y = cost (x, y)  -- V at 0 step is a cost 
fv n x y = minimum $ fqmem x y (n - 1) 

결과 역설 약간의

그래서 먼저 비 memoized 초기 구현입니다. 그것은 memoized 재귀 구현보다 3 배 느리다. 하나의 함수 (즉, fq) 만 메모하고 fv를 건드리지 않으면 결과가 2 배 느려집니다. memcombinators를 더 많이 메모할수록 계산 속도가 느려집니다. 그리고 첫 번째와 두 번째 호출간에 차이가 없습니다.

마지막 질문입니다. Monad.Memo 또는 memcombinators 또는 MemotTrie 중에서 선택하는 이유는 무엇입니까? 댓글에 마지막 2 개를 사용하는 것이 중요합니다. Monad.Memo가 더 나은 선택 인 상황은 무엇입니까?

Answer 1

마지막으로 MemoTrie이 작업을 수행했습니다. 첫 번째 호출시 Monad.Memo보다 빠르며 (훨씬 빠름) 연속 호출시 거의 시간이 걸리지 않습니다!

그리고 코드에 그쪽으로 변화는 사소한는 모나드 접근 방식과 비교 :

아직

import Data.MemoTrie 

type Pos = (Int, Int) 

-- we are moving to (0,0) as we can always shift the world by substituting variables 
-- due to symmetry it is enougth to solve for only positive x and y 

dynamic :: Int -> Int -> [Int] 
dynamic x y = lastUnique $ map (fqmem x y) [1 ..] 
    where lastUnique (x0:x1:xs) | x0 == x1 = x0 
           | otherwise = lastUnique (x1:xs) 

fqmem = memo3 fq 
fvmem = memo3 fv 

fq :: Int -> Int -> Int -> [Int] 
fq _ _ 0 = [0, 0, 0, 0]   -- Q at 0 step is 0 in all directions 
fq x y n = (cost (x, y) +) . (uncurry $ fvmem n) <$> neighbours (x, y) 

fv :: Int -> Int -> Int -> Int 
fv _ 0 0 = 0    -- V at (0, 0) is 0 at any atep 
fv 0 x y = cost (x, y)  -- V at 0 step is a cost 
fv n x y = minimum $ fqmem x y (n - 1) 

cost :: Pos -> Int 
cost (x, y) = abs x + abs y 

neighbours :: Pos -> [Pos] 
neighbours (x, y) = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)] 

내가 Monad.Memo 사용의 이점과 그에 대한 사용 사례는 무엇 무엇인지 알고 싶습니다? 아니면 MemoTrie와 함께 쓸모 없게됩니까?

Memocombinators가 저에게 효과가 없었던 이유는 무엇입니까?

Monad.Memo, Memocombinators 또는 MemoTrie 중에서 엄지 손가락 규칙은 무엇입니까?