優化遞歸函數性能（歐拉15：格子路徑）

我正在嘗試解決項目eulers第15個問題，格子路徑（http://projecteuler.net/problem=15）。優化遞歸函數性能（歐拉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

這工作，速度很快，但我認爲它真的很醜。所以，我想了一會兒，並用更地道的功能上來（請糾正我，如果我犯了這個錯誤），即sovles問題使用遞歸：

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它都會記住舊的結果？

來源

2013-10-13 sra

這個問題有非常簡單的組合答案。 – swish

它不會記憶以前的結果。如果你想使你的解決方案工作，你需要建立一些數組並遞歸地調用它的值。 – swish

你有沒有聽說過可靠的80列規則？你可以在這裏做。 http://www.emacswiki.org/emacs/EightyColumnRule – AJFarmar

現在可以通過數學方法解決這個問題，將重現關係操縱爲一個封閉的形式，但我會專注於更有趣的問題，記憶。

首先，我們可以使用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-13 13:28:06 jozefg

這是否意味着，在Haskell中，簡單函數根本就沒有記憶，只有通過將函數應用到某個懶惰列表中的下一個值才能實現？ – sra

@sra Haskell不會記憶，因爲它只是內存密集。它確實共享函數參數（例如，通過名稱與共享調用），但它就是這樣 – jozefg

它不是通過在懶惰列表中應用函數來記憶，而是通過填充數組使得每個值都依賴於數組中的先前值，這樣，懶惰確保每個計算一次。 – jozefg

這個答案確實很慢，因爲它取決於多個遞歸同時進行。

讓我們來看看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

這筆款項是你的最終結果。但是，上述總和中的每一個都是一個或多個函數調用的結果。所以你的功能將被評估的次數比結果的價值更高。

現在考慮lattice 20 20產量約1500億（這是一個估計，所以我不會太多）。

這意味着您的功能被評估大約150億000 000次。

哎呀。

不要爲這個錯誤感到不好。我曾經說過：

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

我鼓勵你要弄清楚爲什麼這是個壞主意。

PS很高興他們沒有要求lattice 40 40。這將花費超過10^23個函數調用，或者至少300萬年。

僅通過計算一側來加速PPS只會減慢執行速度，因爲函數調用的數量不會減少，但每個函數調用的時間將會減少。

免責聲明：這是我見過的第一塊Haskell代碼。

來源

2015-01-22 17:04:39 Gerwin

優化遞歸函數性能（歐拉15：格子路徑）

回答

相關問題