Haskell：順序斐波那契比並行更快

所以，我在Haskell中嘗試了並行性。我採用了連續和並行實現Fibonacci序列方法的經典示例。這裏是我的Main.hs文件：Haskell：順序斐波那契比並行更快

module Main where 
import Control.Parallel 
main = print (fib 47) 
fib :: Int -> Int 
fib n 
| n <=1 = n 
| otherwise = fib (n-1) + fib (n-2)

我編譯ghc -O2 --make Main.hs -threaded -rtsopts 與time ./Main +RTS -N4執行，給了我：

2971215073 
63.23user 13.03system 0:20.30elapsed 375%CPU (0avgtext+0avgdata 3824maxresident)k 
0inputs+0outputs (0major+276minor)pagefaults 0swaps

因此，與正常的斐波那契數大約需要20秒。

現在，如果我改變我的FIB方法

pfib :: Int -> Int 
pfib n 
    | n <= 1 = n 
    | otherwise = n1 `par` (n2 `par` n1 + n2) 
     where 
      n1 = pfib (n - 1) 
      n2 = pfib (n - 2)

編譯和上面跑，time花費程較長，並與輸出完成：

2971215073 
179.50user 9.04system 0:53.08elapsed 355%CPU (0avgtext+0avgdata 6980maxresident)k 
0inputs+0outputs (0major+1066minor)pagefaults 0swaps

進一步修改我PFIB使用pseq代替第二個par,time給出：

2971215073 
113.34user 3.42system 0:30.91elapsed 377%CPU (0avgtext+0avgdata 7312maxresident)k 
0inputs+0outputs (0major+1119minor)pagefaults 0swaps

我的代碼有問題嗎？爲什麼我在各種實現之間有那麼不合邏輯的時間差？

來源

2017-02-16 jrsall92

從文檔par：

而且這是一個好主意，以確保不是一個簡單的計算，否則並行產卵它的成本黯然失色通過並行運行它獲得的好處。

一個加法和一對減法是一個微不足道的計算。如果你只運行幾個級別的深度，你會看到好處：

module Main where 
import Control.Parallel 

main = print (pfib 16 47) 

fib :: Int -> Int 
fib n 
    | n <= 1 = n 
    | otherwise = fib (n-1) + fib (n-2) 

pfib :: Int -> Int -> Int 
pfib 1 n = fib n 
pfib p n 
    | n <= 1 = n 
    | otherwise = n1 `par` (n2 `par` n1 + n2) 
     where 
      n1 = pfib (p - 1) (n - 1) 
      n2 = pfib (p - 1) (n - 2)

來源

2017-02-16 03:41:02 Ryan

事實上，我發現使用你的代碼有了很大的改進，但是當我使用mymap和myparmap函數時：我的地圖f（x：xs）= fx：mymap f xs myparmap ::（a）我的地圖f（x：xs）= fx：mymap fxs mymap - > b] - > [a] - > [b] myparmap f [] = [] myparmap f（x：xs）= n2'par'（n1'par'n2：n1）其中 n1 = myparmap f xs n2 = fx' 代碼確實在並行版本中速度更快ñ。這是否意味着在這種情況下，在'myparmap'內使用並行版本更有意義，與'pfib'相反？ – jrsall92

@ jrsall92：如果你的任務足夠大以至於在列表元素中並行運行它（顯然是你的測試的情況）並且你想利用更多的內核來加速它，那麼是的。 – Ryan

Haskell：順序斐波那契比並行更快

回答

相關問題