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：顺序斐波那契比并行更快

回答

相关问题