Haskell性能调优

Question

我对Haskell很新,为了更好地学习它,我开始在这里和那里解决问题,我最终得到了这个(项目Euler 34).

145是一个奇怪的数字,为1!+ 4!+ 5!= 1 + 24 + 120 = 145.

求所有数字的总和等于其数字的阶乘>的总和.

注意:为1!= 1和2!= 2不是它们不包括在内的总和.

我写了一个C和一个Haskell蛮力解决方案.

有人可以解释一下,Haskell版本比C实现慢〜15x(~0.450 s 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;
}

这里是haskell解决方案

--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秒.这已经很不错了.

如果我们要做得更好,我们应该先更换div用quot和mod用rem.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秒.