stu*_*ith 25 c performance haskell
我正在研究Project Euler中的问题,作为学习Haskell的一种方式,我发现我的程序比同类C版本慢很多,即使在编译时也是如此.我该怎么做才能加速我的Haskell程序？
例如,我对问题14的强力解决方案是:
import Data.Int
import Data.Ord
import Data.List
searchTo = 1000000
nextNumber :: Int64 -> Int64
nextNumber n
| even n = n `div` 2
| otherwise = 3 * n + 1
sequenceLength :: Int64 -> Int
sequenceLength 1 = 1
sequenceLength n = 1 + (sequenceLength next)
where next = nextNumber n
longestSequence = maximumBy (comparing sequenceLength) [1..searchTo]
main = putStrLn $ show $ longestSequence
这需要大约220秒,而"等效"暴力C版本只需要1.2秒.
#include <stdio.h>
int main(int argc, char **argv)
{
int longest = 0;
int terms = 0;
int i;
unsigned long j;
for (i = 1; i <= 1000000; i++)
{
j = i;
int this_terms = 1;
while (j != 1)
{
this_terms++;
if (this_terms > terms)
{
terms = this_terms;
longest = i;
}
if (j % 2 == 0)
j = j / 2;
else
j = 3 * j + 1;
}
}
printf("%d\n", longest);
return 0;
}
我究竟做错了什么？或者我天真地认为Haskell甚至可以接近C的速度？
(我正在使用gcc -O2编译C版本,使用ghc -make -O编译Haskell版本).
ken*_*ytm 24
出于测试目的,我刚刚设置searchTo = 100000.所需时间为7.34秒.一些修改会带来一些重大改进:
使用Integer而不是Int64.这将时间提高到1.75秒.
使用累加器(你不需要sequenceLength是懒惰的吗？)1.54s.
seqLen2 :: Int -> Integer -> Int
seqLen2 a 1 = a
seqLen2 a n = seqLen2 (a+1) (nextNumber n)
sequenceLength :: Integer -> Int
sequenceLength = seqLen2 1
重写nextNumber使用quotRem,从而避免计算两次除法(一次进入even和进入一次div).1.27s.
nextNumber :: Integer -> Integer
nextNumber n
| r == 0 = q
| otherwise = 6*q + 4
where (q,r) = quotRem n 2
使用Schwartzian变换代替maximumBy.问题maximumBy . comparing是sequenceLength每个值都会多次调用该函数.0.32s.
longestSequence = snd $ maximum [(sequenceLength a, a) | a <- [1..searchTo]]
注意:
ghc -O并运行+RTS -s)gcc -O3 -m32.Dan*_*her 11
虽然这已经相当陈旧了,但让我说一下,有一个关键点以前没有解决过.
首先,我的盒子上的不同程序的时间.由于我使用的是64位Linux系统,它们显示出一些不同的特性:使用Integer而不是Int64像32位GHC一样改善性能,其中每次Int64操作都会产生C调用的成本而计算如果Integer符合有符号的32位整数,则不需要外部调用(因为这里只有少数操作超出该范围,Integer因此在32位GHC上是更好的选择).
Integer而不是Int64:33.96秒Int:1.85秒Int:1.90秒quotRem而不是divMod:1.79秒那我们有什么？
divresp.divMod什么时候没必要,quot分别说.quotRem要快得多什么仍然缺少？
if (j % 2 == 0)
j = j / 2;
else
j = 3 * j + 1;
我使用的任何C编译器都将测试j % 2 == 0转换为位掩码,不使用除法指令.GHC(尚未)这样做.因此,测试even n或计算n `quotRem` 2是一项非常昂贵的操作.用nextNumberKennyTM 替换Integer版本
nextNumber :: Integer -> Integer
nextNumber n
| fromInteger n .&. 1 == (0 :: Int) = n `quot` 2
| otherwise = 3*n+1
将其运行时间减少到3.25秒(注意:对于Integer,n `quot` 2快于n `shiftR` 1,需要12.69秒!).
在Int版本中执行相同操作会将其运行时间减少到0.41秒.对于Ints,除以2的位移比quot操作快一点,将其运行时间减少到0.39秒.
消除列表的构造(也不会出现在C版本中),
module Main (main) where
import Data.Bits
result :: Int
result = findMax 0 0 1
findMax :: Int -> Int -> Int -> Int
findMax start len can
| can > 1000000 = start
| canlen > len = findMax can canlen (can+1)
| otherwise = findMax start len (can+1)
where
canlen = findLen 1 can
findLen :: Int -> Int -> Int
findLen l 1 = l
findLen l n
| n .&. 1 == 0 = findLen (l+1) (n `shiftR` 1)
| otherwise = findLen (l+1) (3*n+1)
main :: IO ()
main = print result
产生更小的加速,导致0.37秒的运行时间.
因此,与C版本密切对应的Haskell版本不会花费那么长的时间,它是~1.3的因子.
好吧,让我们公平一点,C版本的效率低下,Haskell版本中没有,
if (this_terms > terms)
{
terms = this_terms;
longest = i;
}
出现在内循环中.将其从C版本的内环中取出可将其运行时间缩短至0.27秒,使得系数达到1.4.
小智 5
比较可能会重新计算sequenceLength太多.这是我最好的版本:
type I = Integer
data P = P {-# UNPACK #-} !Int {-# UNPACK #-} !I deriving (Eq,Ord,Show)
searchTo = 1000000
nextNumber :: I -> I
nextNumber n = case quotRem n 2 of
(n2,0) -> n2
_ -> 3*n+1
sequenceLength :: I -> Int
sequenceLength x = count x 1 where
count 1 acc = acc
count n acc = count (nextNumber n) (succ acc)
longestSequence = maximum . map (\i -> P (sequenceLength i) i) $ [1..searchTo]
main = putStrLn $ show $ longestSequence
答案和时间比C慢,但它确实使用任意精度整数(通过Integer类型):
ghc -O2 --make euler14-fgij.hs
time ./euler14-fgij
P 525 837799
real 0m3.235s
user 0m3.184s
sys 0m0.015s