Haskell性能調優

Question

我是Haskell的新手，爲了更好地學習它，我開始在這裏和那裏解決問題，最後我得到了這個結果（project Euler 34）。

145是一個奇怪的數字，爲1！ + 4！ + 5！ = 1 + 24 + 120 = 145.

找到所有數字的總和，它們等於它們的位數的階乘>之和。

注意：如1！ = 1和2！ = 2不是它們不包括在內的總和。

我寫了一個C和一個Haskell蠻力解決方案。

有人能解釋我的Haskell版本比C實現慢15x（〜0.450s vs 6.5s），以及如何調整和加速Haskell解決方案？

unsigned int solve(){ 
unsigned int result = 0; 
unsigned int i=10; 
while(i<2540161){ 
    unsigned int sumOfFacts = 0; 
    unsigned int number = i; 
    while (number > 0) { 
     unsigned int d = number % 10; 
     number /= 10; 
     sumOfFacts += factorial(d); 
    } 

    if (sumOfFacts == i) 
     result += i; 

    i++; 
} 
return result; 
} 

這裏的哈斯克爾解決方案

--BRUTE FORCE SOLUTION 
solve:: Int 
solve = sum (filter (\x-> sfc x 0 == x) [10..2540160]) 

--sum factorial of digits 
sfc :: Int -> Int -> Int 
sfc 0 acc = acc 
sfc n acc = sfc n' (acc+fc r) 
    where 
     n' = div n 10 
     r = mod n 10 --n-(10*n') 
     fc 0 =1 
     fc 1 =1 
     fc 2 =2 
     fc 3 =6 
     fc 4 =24 
     fc 5 =120 
     fc 6 =720 
     fc 7 =5040 
     fc 8 =40320 
     fc 9 =362880 

Answer 1

首先，優化編譯。對於ghc-7.10.1 -O2 -fllvm，Haskell版本對我來說運行在0.54秒。這已經很不錯了。

如果我們要做得更好，我們應該先quot和mod與rem取代div。 div和mod做了一些額外的工作，因爲它們以不同的方式處理負數的四捨五入。由於我們在這裏只有正數，我們應該切換到更快的功能。

其次，我們應該用數組查找替換fc中的模式匹配。 GHC使用Int模式的分支結構，並在案例數足夠大時使用二分法搜索。通過查找，我們可以在這裏做得更好。

新的代碼如下所示：

import qualified Data.Vector.Unboxed as V 

facs :: V.Vector Int 
facs = 
    V.fromList [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880] 

--BRUTE FORCE SOLUTION 
solve:: Int 
solve = sum (filter (\x-> sfc x 0 == x) [10..2540160]) 

--sum factorial of digits 
sfc :: Int -> Int -> Int 
sfc 0 acc = acc 
sfc n acc = sfc n' (acc + V.unsafeIndex facs r) 
    where 
     (n', r) = quotRem n 10 

main = print solve 

它運行在我的電腦上0.095秒。