ハスケルでの相互再帰のためのMonad.Memoのメモ帳

Question

私はHaskellでいくつかの動的再帰実装を行っています。

私はメモを使って物事をスピードアップすることに決めました。

Monad.Memoは、正確なケースのMemoTトランスを提供しています。しかし、格納された値の内部表現としてMapを使用します。そして、これは私に大きさのスピードブーストを与えましたが、まだ十分ではありません。

libは内部ストレージとしての配列ベースおよびベクトルベースの実装をサポートしていますが、単純な再帰でのみ機能し、MemoTのような相互再帰用のトランスは見つかりませんでした。

効率的なベクトルベースの内部表現（存在する場合）を使って相互再帰メモを行う最良の方法は何ですか？

私の次の質問はメモ効果に関するものです。だから私は最初の走りでは時間がかかると思っていました。しかし、私がghciでそれを実行するのが毎回の時間と同じであることがわかった。最初と2番目のランの違いはありません。私は以下のように時間を測定しました：

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を試してみました。 memizationへ

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

そして、私の試み（変更された部分のみ）：

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) 

結果パラドックスのビット

だから、最初は非メモ化初期の実装です。これは、メモのない再帰的実装よりも3倍遅くなります。 1つの関数（すなわち、fq）のみをメモしてfvに触れないと、結果は2倍遅くなります。私がmemcombinatorsをメモするほど、計算は遅くなります。また、最初と2番目の呼び出しの間に違いはありません。

最後の質問です。 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を選択する際の経験則は何ですか？