爲什麼這個遞歸很慢？

多少種方法那裏$ 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

爲什麼這個遞歸很慢？

回答

相關問題