0

我正在尝试解决项目欧拉第 15 个问题，晶格路径（http://projecteuler.net/problem=15）。

我的第一次尝试是逐行解决问题，然后在最后一行中取最后一个元素。

number_of_ways_new_line last_line = foldl calculate_values [] last_line
                                    where
                                      calculate_values lst x = lst ++ [(if length lst > 0 then (last lst) + x else head last_line)]

count_ways x = foldl (\ lst _ -> number_of_ways_new_line lst) (take x [1,1..]) [1..x-1]

result_15 = last $ count_ways 21

这行得通而且速度很快，但我认为它真的很难看。所以我想了一会儿，想出了一个更惯用的函数（如果我弄错了，请纠正我），它使用递归来解决问题：

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

这适用于短数字，但它根本无法扩展。lattice 1 2我通过使用和lattice 2 1将永远相同的事实对其进行了一点优化。为什么这么慢？Haskell 不是在记忆以前的结果，所以无论何时lattice 2 1调用它都会记住旧的结果？

4

2 回答 2

2

现在这个问题可以通过将递归关系处理成一个封闭的形式在数学上解决，但我将专注于更有趣的问题，记忆。

首先我们可以使用Data.Array（这是懒惰的）

 import Data.Array as A

 lattice x y = array ((0, 0), (x, y)) m ! (x, y)
   where m = [(,) (x, y) (lattice' x y) | x <- [0..x], y <- [0..y]
         lattice' 0 0  = 1
         lattice' x 0 = lattice (x-1) 0
         lattice' 0 y = lattice (y-1) 0
         lattice' x y | x >= y    = (lattice (x-1) y) + (lattice x (y-1))
                      | otherwise = (lattice y (x-1)) + (lattice (y-1) x)

现在这些重复通过映射，但是，由于映射是惰性的，一旦映射条目被评估，它的 thunk 将被突变为一个简单的值，确保它只计算一次。

我们也可以使用美妙的memo-combinators图书馆。

 import Data.MemoCombinators as M
 lattice = memo2 M.integral M.integral lattice'
   where lattice' 0 0 = 1
         lattice' x 0 = lattice (x-1) 0
         lattice' 0 y = lattice (y-1) 0
         lattice' x y | x >= y    = lattice (x-1) y + lattice x (y-1)
                      | otherwise = lattice y (x-1) + lattice (y-1) x
于 2013-10-13T13:28:06.020 回答
1

这个答案确实很慢，因为它同时依赖于多个递归。

让我们检查一下这个lattice功能。它有什么作用？它返回两个lattice函数的总和、另一个lattice函数或第一个函数。

现在让我们来看一个例子：lattice 2 2.
这等于lattice 1 2 + lattice 2 1。
这等于lattice 0 2 + lattice 1 1 + lattice 1 1 + lattice 2 0。
这等于...

你意识到问题了吗？在您的代码中没有一种乘法或添加常量的情况。这意味着整个函数将归结为：

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + ... + 1

这个总和就是你的最终结果。但是，上述总和中的每一个 1 都是一个或多个函数调用的结果。因此，您的函数的评估频率将超过结果的价值。

现在考虑一下lattice 20 20大约 1500 亿的收益（这是一个估计值，所以我不会剧透太多）。

这意味着您的函数会被评估大约 150 000 000 000 次。

哎呀。

不要为这个错误感到难过。我曾经说过：

fibbonaci x = fibbonaci (x-1) + fibbonaci (x-2)

我鼓励你弄清楚为什么这是一个坏主意。

PS很高兴他们没有要求lattice 40 40。那将需要超过 10^23 个函数调用，或者至少 300 万年。

PPS 通过只计算一侧的加速度只会减慢执行速度，因为函数调用的数量不会减少，但是每个函数调用的时间会减少。

免责声明：这是我见过的第一段 Haskell 代码。

于 2015-01-22T17:04:39.860 回答