我是 Haskell 的新手,为了更好地学习它,我开始到处解决问题,最后得到这个 ( project Euler 34)。
145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.
Find the sum of all numbers which are equal to the sum of the factorial >of their digits.
Note: as 1! = 1 and 2! = 2 are not sums they are not included.
我写了一个 C 和一个 Haskell 暴力解决方案。
有人可以向我解释 Haskell 版本比 C 实现慢 ~15 倍(~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
最佳答案
首先,进行优化编译。使用 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 秒。
关于performance - Haskell 性能调整,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29413564/