5

我一直在学习一些 Haskell，并且边做边做项目 Euler 问题。我并不真正关心欧拉问题的答案（我可以很高兴地使用蛮力，或者用其他语言来解决），而是方法。

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

我会说这个想法是记忆（sp？）函数的想法是相当明显的，但我不确定该怎么做。我用谷歌搜索，在 Haskell Cafe 上发现了这个，我天真地试图适应，但最终得到：

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 记忆是如何工作的。

以我的代码为例，是否有人愿意解释a）为什么我的代码这么慢
b）应该如何完成（不使用可变变量，这是我遇到的一个解决方案）
c）在这种情况下memoization如何工作？

4

3 回答 3

10

在我看来，“记忆”被高度高估了。没有一种万能的记忆技术（在任何编程语言中）可以将每个单一案例的计算变成一般的计算。您必须了解每个问题，并组织事物以控制您需要使用的内存量。

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

在 Haskell 中，懒惰非常适合这种情况。它免除了您跟踪准确记住什么和忘记什么的所有工作 - 只需计算所有可能矩形的总数的无限网格，然后让 Haskell 完成剩下的工作。

对于零行，您只有底线。不管多长，到尽头的路只有一条，所以路数为 repeat 1。

要从上一行计算网格中的一行，首先1 （只有一条路径直接向下，无论您有多高），然后在每一步中，将上一行中的相应条目和上一步中的上一步相加当前行。总之，我们有：

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

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

于 2010-08-01T13:44:43.753 回答
5

折腾几个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)
内存：（2,2）
路线：（2,2）
内存：（1,2）
路线：（1,2）
内存：（0,2）
内存：（1,1）
路线：（1,1）
内存：（0,1）
内存：（1,0）
内存：（2,1）
路线：（2,1）
内存：（1,1）
路线：（1,1）
内存：（0,1）
内存：（1,0）
内存：（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

请注意，算法是不正确的，但至少很容易快速得到错误的答案！

于 2010-08-01T00:07:56.707 回答
0

发生的情况是，每次调用 memRoute 时都会重新计算您的记忆表。不是全部（幸运的是！），但至少在一次通话中完成的工作不会与其他人共享。我能想到的最简单的重写是：

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

这与您表达的意图非常接近，但我认为有更好的方法来进行记忆，通过使用 aData.Map并让实际的调用模式决定记忆哪些值。

于 2010-08-02T15:29:28.400 回答