为什么这个递归很慢？

多少种方法那里$ 50，只用1C，5C，10C，25C，50C或硬币？

这里是我的代码：

main = print $ coinCombinations [1,5,10,25,50] !! 5000 

coinCombinations coins = foldr recurse (1 : repeat 0) coins 
    where recurse a xs = take a xs ++ zipWith (+) (drop a xs) (recurse a xs)

事实证明，我的recurse功能是缓慢的，也许二次时间或更糟。但我不明白为什么，因为它看起来与斐波那契列表

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

来源

2016-04-18 zoko

只是猜测这与你在递归的每一步中使用take和drop有很大关系。这些是“O（a）”功能，也许尝试splitAt会是更好的选择。另外，请记住++也是一个“O（a）”操作，因为连接不是使用指针算法完成的，而是通过遍历整个结构。 –

我以为可能是这样，但后来我尝试了一个简单的'recurseone xs = head xs：zipWith（+）（tail xs）（recurseone xs）'并且它仍然很慢 – zoko

您是否明白为什么您的代码在第一名？通常，您可以从正确性证明（正确性属性的“终止”部分）推断资源使用情况（即复杂性约束）。 – d8d0d65b3f7cf42

递归的问题是，护理需要注意不要成倍分支或有指数内存足迹;并且还写了一个尾递归函数通常不太具有表现力。

您可以通过动态编程绕过整个递归开销;其具有使用权利折叠在Haskell非常高性能的实现：

count :: (Num a, Foldable t) => t Int -> Int -> a 
count coins total = foldr go (1: repeat 0) coins !! total 
    where 
    go coin acc = out where out = zipWith (+) acc $ replicate coin 0 ++ out

然后：

\> count [1, 5, 10, 25, 50] 5000 
432699251

或如31st problem of Project Euler^（1）：

\> count [1, 2, 5, 10, 20, 50, 100, 200] 200 
73682

甲更少高效的替代方法是使用不可变的非严格（盒装）阵列：

import Data.Array (listArray, (!)) 

count :: (Num a, Foldable t) => t Int -> Int -> a 
count coins total = foldr go init coins ! total 
    where 
    init = listArray (0, total) $ 1: repeat 0 
    go coin arr = out 
     where 
     out = listArray (0, total) $ map inc [0..total] 
     inc i = arr ! i + if i < coin then 0 else out ! (i - coin)

_{（1）的问题已经在别处公布在计算器;见Using dynamic programming in Haskell? [Warning: ProjectEuler 31 solution inside]}

来源

2016-04-18 17:25:06

这看起来几乎和我的代码+ Derek的编辑完全一样......唯一的区别是你在前面添加了零，然后添加，而我使用前面的“xs”。所以我认为它会有同样的表现。 – zoko

你是对的，这是二次时间。问题是

不是一回事

foo a = r 
      +-------+ 
      v  v 
    where r = bar r

在第一种情况中，两个foo功能是指相同的对象，但在第二，的foo的结果指的是同一个对象。所以在第一种情况下，如果bar想要参考foo a的一部分它已经计算出来了，它必须再次计算整个事情。

来源

2016-06-04 14:11:44 Dan

为什么这个递归很慢？

回答

相关问题