代码之家 › 专栏 › 技术社区 › Squidly

回忆录与Haskell的Euler问题15计划

memoization haskell

5

Squidly · 技术社区 · 15 年前

我一直在学习一些Haskell,并且边走边做projecteuler问题。我并不是真的为欧拉问题的答案而烦恼(我可以很高兴地用蛮力,或者用其他语言),而是方法。

我坚持在合理的时间内做第15题。它要求从20x20网格的左上角到右下角的非回溯路由的数量。 Link here

我想说,很明显,这个想法是要记忆(sp?)函数,但我不确定该怎么做。我搜索了一下,发现 this

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)

以我的代码为例,有人愿意解释一下为什么我的代码这么慢吗
b) 应该怎么做(不使用可变表,这是我遇到的一个解决方案)
c) 在这种情况下,回忆录是如何工作的?

3 回复 | 直到 10 年前

1

5

Greg Bacon 15 年前

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

重用子计算是非常重要的 dynamic programming .

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

2

10

Yitz 15 年前

在我看来,“回忆录”被高估了。根本没有一刀切的记忆技术(在任何编程中) 组织事情来控制你需要的内存量使用。

在本例中,要获取 n x m 你不需要记住每个人的总数 全部的 较小的矩形, 只适用于两个方向都小一步的矩形。所以你可以一行一行地建立,忘记所有的总数小矩形。

在哈斯克尔,懒惰是完美的这种情况。它缓解了你已经完成了所有的工作,记下到底要记住什么忘了什么-只需计算一个无限的总网格所有可能的矩形,让Haskell做剩下的工作。

到终点只有一条路,所以路的数目是有限的 repeat 1

要从上一行计算网格中的一行,可以从 1 (不管你有多高,只有一条路直走), 然后在每个步骤中,将

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

它在GHCi提示下为我即时计算出答案。

3

0

yatima2975 15 年前

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

这与你所表达的意图非常接近,但我认为有更好的方法可以通过使用 Data.Map