16

次の関数をメモ化しようとしています。

gridwalk x y
    | x == 0 = 1
    | y == 0 = 1
    | otherwise = (gridwalk (x - 1) y) + (gridwalk x (y - 1))

これを見て、私は次の解決策を思いつきました：

gw :: (Int -> Int -> Int) -> Int -> Int -> Int
gw f x y
    | x == 0 = 1
    | y == 0 = 1
    | otherwise = (f (x - 1) y) + (f x (y - 1))

gwlist :: [Int]
gwlist = map (\i -> gw fastgw (i `mod` 20) (i `div` 20)) [0..]

fastgw :: Int -> Int -> Int
fastgw x y = gwlist !! (x + y * 20)

私はそれからこのように呼ぶことができます：

gw fastgw 20 20

Haskellで複数のパラメーターを持つ関数をメモ化するためのより簡単で簡潔で一般的な方法（gwlistメモ化リストにアクセスできるように2Dから1D空間に変換するために関数の最大グリッド次元をハードコーディングする必要があることに注意してください）はありますか？

4

4 に答える 4

19

リストのリストを使用して、両方のパラメーターの関数の結果をメモ化できます。

memo :: (Int -> Int -> a) -> [[a]]
memo f = map (\x -> map (f x) [0..]) [0..]


gw :: Int -> Int -> Int
gw 0 _ = 1
gw _ 0 = 1
gw x y = (fastgw (x - 1) y) + (fastgw x (y - 1))

gwstore :: [[Int]]
gwstore = memo gw

fastgw :: Int -> Int -> Int
fastgw x y = gwstore !! x !! y
于 2011-04-05T14:19:48.777 に答える
9

hackageのdata-memocombinatorsパッケージを使用してください。それは使いやすい暗記技術を提供し、それらを使用するための簡単で簡潔な方法を提供します：

import Data.MemoCombinators (memo2,integral)

gridwalk = memo2 integral integral gridwalk' where
  gridwalk' x y
    | x == 0 = 1
    | y == 0 = 1
    | otherwise = (gridwalk (x - 1) y) + (gridwalk x (y - 1))
于 2011-04-05T15:06:51.980 に答える
5

MemoTrieパッケージから関数をメモ化するためにData.MemoTrie使用するバージョンは次のとおりです。

import Data.MemoTrie(memo2)

gridwalk :: Int -> Int -> Int
gridwalk = memo2 gw
  where
    gw 0 _ = 1
    gw _ 0 = 1
    gw x y = gridwalk (x - 1) y + gridwalk x (y - 1)
于 2011-04-05T15:12:35.693 に答える
3

最大の一般性が必要な場合は、メモ化機能をメモ化できます。

memo :: (Num a, Enum a) => (a -> b) -> [b]
memo f = map f (enumFrom 0)

gwvals = fmap memo (memo gw)

fastgw :: Int -> Int -> Int
fastgw x y = gwvals !! x !! y

この手法は、任意の数の引数を持つ関数で機能します。

編集：元のコードのバグを指摘してくれたPhilipK.に感謝します。元々memoは「Num」ではなく「Bounded」制約があり、で列挙を開始しましたminBound。これは自然数に対してのみ有効です。

ただし、リストは線形ルックアップの複雑さがあるため、メモ化に適したデータ構造ではありません。MapまたはIntMapを使用した方がよい場合があります。またはHackageを見 て ください。

この特定のコードは怠惰に依存していることに注意してください。したがって、マップの使用に切り替えたい場合は、次のように、リストから限られた量の要素を取得する必要があります。

gwByMap :: Int -> Int -> Int -> Int -> Int
gwByMap maxX maxY x y = fromMaybe (gw x y) $ M.lookup (x,y) memomap
 where
  memomap = M.fromList $ concat [[((x',y'),z) | (y',z) <- zip [0..maxY] ys]
                                              | (x',ys) <- zip [0..maxX] gwvals]

fastgw2 :: Int -> Int -> Int
fastgw2 = gwByMap 20 20

この場合、ghcは共有について愚かかもしれないと思います。次のようにx、yパラメータを削除する必要があるかもしれません。

gwByMap maxX maxY = \x y -> fromMaybe (gw x y) $ M.lookup (x,y) memomap
于 2011-04-05T14:46:18.490 に答える