Haskell中的Memoization&Project Euler Problem 15

Question

我一直在学习一些Haskell,并且在我去的时候做项目的Euler问题.对于欧拉问题的答案(我可以高兴地蛮力,或者用其他语言做),我并不是真正的烦恼,而是方法.

我在合理的时间内坚持做问题15.它要求从20x20网格的左上角到右下角的非回溯路线的数量.链接在这里

我会说这个想法很容易记住(sp？)函数,但我不确定如何去做.我用谷歌搜索,并在Haskell咖啡馆遇到这个我天真地试图适应,但最终得到:

memRoute :: (Int,Int) -> Int
memRoute (x,y) = fromJust $ lookup (x,y) $ map (\t -> (t,route t)) [(x,y) | x <- [0..20], y <- [0..20]]

route (0,0) = 0
route (_,0) = 1
route (0,_) = 1
route (x,y) = memRoute (x-1,y) + memRoute (x,y-1)

这看起来很糟糕,并且表现得非常糟糕(比天真的版本慢很多).问题是我真的不明白Haskell的memoization是如何工作的.

使用我的代码作为例子,任何人都可以解释a)为什么我的速度太慢
b)应该怎么做(没有使用mutables,这是我遇到的解决方案)
c)在这种情况下memoization 如何工作？

Answer 1

在我看来,"备忘录"被高估了.没有一种通用的记忆技术(在任何编程语言中)将每个单例计算转换为一般计算.您必须了解每个问题,并组织事物来控制您需要使用的内存量.

在这种情况下,要获取n x m矩形的路径数,您不需要记住所有较小矩形的总数,只需要记住在任一方向上小一步的矩形.因此,您可以逐行构建,忘记所有较小矩形的总计.

在哈斯克尔,懒惰对于这种情况是完美的.它让你无法完成记录要记住什么以及忘记什么的所有工作 - 只需为所有可能的矩形计算总数的无限网格,让Haskell完成剩余的工作.

对于零行,您只有底线.无论多长时间,只有一条路径到达目的地,所以路径的数量是 repeat 1.

要从前一行计算网格中的行,您可以从1 (只有一个路径直接向下,无论您有多高)开始,然后在每个步骤中将上一行中的相应条目和上一行中的相应条目相加.当前行.总而言之,我们有:

iterate (scanl (+) 1 . tail) (repeat 1) !! 20 !! 20

这会在GHCi提示下立即为我计算答案.

Answer 2

折腾了trace几点

memRoute :: (Int,Int) -> Int
memRoute (x,y) = trace ("mem: " ++ show (x,y))
                 fromJust $
                 lookup (x,y) $
                 map (\t -> (t,route t))
                 [(x,y) | x <- [0..20], y <- [0..20]]

route (0,0) = 0
route (_,0) = 1
route (0,_) = 1
route (x,y) = trace ("route: " ++ show (x,y))
              memRoute (x-1,y) + memRoute (x,y-1)

看你根本没有记忆.

ghci> memRoute (2,2)
mem: (2,2)
route: (2,2)
mem: (1,2)
route: (1,2)
mem: (0,2)
mem: (1,1)
route: (1,1)
mem: (0,1)
mem: (1,0)
mem: (2,1)
route: (2,1)
mem: (1,1)
route: (1,1)
mem: (0,1)
mem: (1,0)
mem: (2,0)
6

重用子计算是动态编程.

import Data.Array

routes :: (Int,Int) -> Int
routes = (rte !)
  where rte = array ((1,1), (n,n))
                    [ ((x,y), route (x,y)) | x <- [1 .. n],
                                             y <- [1 .. n] ]
        route (1,1) = 0
        route (_,1) = 1
        route (1,_) = 1
        route (x,y) = rte ! (x-1,y) + rte ! (x,y-1)
        n = 20

请注意,算法不正确,但至少很快就会得到错误的答案!